题目描述
给定一个N×NN \times NN×N的字符网格（N≤50N \le 50N≤50），每个格子可包含任意可打印ASCII\texttt{ASCII}ASCII字符（ASCII\texttt{ASCII}ASCII码323232到126126126，包含空格）。随后给出若干个待查找的单词（长度111到NNN，不含空格）。单词在网格中的出现定义为：从某个格子开始，沿着八个方向之一（北、东北、东、东南、南、西南、西、西北）移动，依次匹配单词的每个字符。移动时，若遇到空格字符，则沿同一方向继续跳过（即忽略空格），直到遇到非空格或越界。查找所有出现位置，按行升序、列升序、方向顺时针顺序输出每个出现（起始坐标和方向）。若无出现，输出not found。每组数据间输出空行，每个单词输出前先输出一个空行。
输入格式
第一行为一个整数，表示数据组数，随后有一个空行。每组数据第一行是一个整数NNN，接下来NNN行每行长度为NNN的字符串（可能包含前导或中间空格，但无尾随空格），表示网格。随后若干行，每行一个单词（不含空格），直到遇到空行或文件结束。每组数据之间无额外标记。
输出格式
对于每个单词，首先输出一个空行，然后输出该单词本身。接着按规则输出所有出现位置，格式为(row,column) - dir，每行一个。若无出现，则输出not found。每组数据结束后输出一个空行（即两组数据之间有一个空行）。
样例输入
1 4 LOST I N SP A C E ANT LOT S PT样例输出
ANT (3,4) - N LOT not found S (1,3) - N (1,3) - NE (1,3) - E (1,3) - SE (1,3) - S (1,3) - SW (1,3) - W (1,3) - NW (3,1) - N (3,1) - NE (3,1) - E (3,1) - SE (3,1) - S (3,1) - SW (3,1) - W (3,1) - NW PT (3,2) - NE题目分析
网格中包含空格，空格在匹配过程中被忽略，相当于路径可以在空格区域自由穿过，但必须保持直线方向。因此匹配一个单词时，从起点出发，沿某个方向每次移动一格，如果当前位置是空格，则继续沿同方向移动，直到找到非空格或越界。每跳过一个空格不消耗字符，只当找到非空格且与单词下一个字符匹配时才消耗一个字符。若未匹配或越界则失败。需要枚举所有起点和八个方向，复杂度O(N2×8×L)O(N^2 \times 8 \times L)O(N2×8×L)，其中LLL为单词长度，最大N=50N=50N=50，完全可行。
解题思路
实现步骤确定如下：
步骤1\texttt{1}1. 读取数据组数，跳过空行。对于每组数据，读取NNN，然后读入NNN行网格，每行可能包含空格，使用getline\texttt{getline}getline读取，并存入二维字符数组。
步骤2\texttt{2}2. 定义方向数组，顺序为N, NE, E, SE, S, SW, W, NW（顺时针）。每个方向对应行、列增量。
步骤3\texttt{3}3. 对于每个单词，输出一个空行和单词本身。然后枚举所有起点(i,j)(i,j)(i,j)，若该格字符与单词第一个字符相同，则对每个方向进行匹配尝试。
步骤4\texttt{4}4. 匹配过程：从起点出发，设当前行、列为(r,c)(r,c)(r,c)，已匹配的单词索引idx=0\textit{idx}=0idx=0。在方向ddd上循环，每次先移动一步到新位置，若越界则失败；若当前位置字符为空格，则继续移动（跳过），不消耗字符；若为非空格，则与单词的下一个字符（idx+1\textit{idx}+1idx+1）比较，若匹配，则idx\textit{idx}idx增加，继续循环；若不匹配，则失败。当idx\textit{idx}idx达到单词长度减111时，匹配成功，记录该起点和方向。
步骤5\texttt{5}5. 所有匹配结果按起点行升序、列升序、方向顺序输出。由于枚举顺序为行、列、方向，且方向顺序固定，输出自然符合要求。若没有匹配，则输出not found。
步骤6\texttt{6}6. 每组数据处理完毕后，输出一个空行（通过if (c>1) cout << '\n'实现）。
代码实现
// Lost in Space// UVa ID: 736// Verdict: Accepted// Submission Date: 2018-03-29// UVa Run Time: 0.010s//// 版权所有（C）2018，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases;charboard[64][64];intn,offset[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};string dirs[8]={"N","NE","E","SE","S","SW","W","NW"};string line,word;cin>>cases;for(intc=1;c<=cases;c++){if(c>1)cout<<'\n';cin>>n;cin.ignore(1024,'\n');for(inti=0;i<n;i++){getline(cin,line);for(intj=0;j<n;j++)board[i][j]=line[j];}while(getline(cin,word),word.length()>0){boolprinted=false;cout<<'\n'<<word<<'\n';for(inti=0;i<n;i++)for(intj=0;j<n;j++){if(board[i][j]==word.front()){for(intk=0;k<8;k++){boolsame=true;intnexti=i,nextj=j;for(intl=1;l<word.length();l++){nexti+=offset[k][0],nextj+=offset[k][1];while(nexti>=0&&nexti<n&&nextj>=0&&nextj<n&&board[nexti][nextj]==' ')nexti+=offset[k][0],nextj+=offset[k][1];if(nexti>=0&&nexti<n&&nextj>=0&&nextj<n&&board[nexti][nextj]==word[l])continue;same=false;break;}if(same){cout<<'('<<(i+1)<<','<<(j+1)<<") - ";cout<<dirs[k]<<'\n';printed=true;}}}}if(!printed)cout<<"not found\n";}}return0;}总结
本题模拟字符串在二维网格中的匹配，关键点在于忽略空格字符，即匹配时自动跳过空格。采用枚举起点和方向，并沿方向步进，遇到空格跳过，直到匹配完整单词或失败。输出顺序按行、列、方向，利用枚举顺序自然满足。注意输入包含空格，需用getline\texttt{getline}getline读取。该算法时间复杂度为O(N3×8)O(N^3 \times 8)O(N3×8)，对于N≤50N \le 50N≤50足够高效。实现简洁，易于扩展。
