UVa 736 Lost in Space

题目描述给定一个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为单词长度最大N50N50N50完全可行。解题思路实现步骤确定如下步骤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)已匹配的单词索引idx0\textit{idx}0idx0。在方向ddd上循环每次先移动一步到新位置若越界则失败若当前位置字符为空格则继续移动跳过不消耗字符若为非空格则与单词的下一个字符idx1\textit{idx}1idx1比较若匹配则idx\textit{idx}idx增加继续循环若不匹配则失败。当idx\textit{idx}idx达到单词长度减111时匹配成功记录该起点和方向。步骤5\texttt{5}5. 所有匹配结果按起点行升序、列升序、方向顺序输出。由于枚举顺序为行、列、方向且方向顺序固定输出自然符合要求。若没有匹配则输出not found。步骤6\texttt{6}6. 每组数据处理完毕后输出一个空行通过if (c1) cout \n实现。代码实现// Lost in Space// UVa ID: 736// Verdict: Accepted// Submission Date: 2018-03-29// UVa Run Time: 0.010s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;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;cincases;for(intc1;ccases;c){if(c1)cout\n;cinn;cin.ignore(1024,\n);for(inti0;in;i){getline(cin,line);for(intj0;jn;j)board[i][j]line[j];}while(getline(cin,word),word.length()0){boolprintedfalse;cout\nword\n;for(inti0;in;i)for(intj0;jn;j){if(board[i][j]word.front()){for(intk0;k8;k){boolsametrue;intnextii,nextjj;for(intl1;lword.length();l){nextioffset[k][0],nextjoffset[k][1];while(nexti0nextinnextj0nextjnboard[nexti][nextj] )nextioffset[k][0],nextjoffset[k][1];if(nexti0nextinnextj0nextjnboard[nexti][nextj]word[l])continue;samefalse;break;}if(same){cout((i1),(j1)) - ;coutdirs[k]\n;printedtrue;}}}}if(!printed)coutnot found\n;}}return0;}总结本题模拟字符串在二维网格中的匹配关键点在于忽略空格字符即匹配时自动跳过空格。采用枚举起点和方向并沿方向步进遇到空格跳过直到匹配完整单词或失败。输出顺序按行、列、方向利用枚举顺序自然满足。注意输入包含空格需用getline\texttt{getline}getline读取。该算法时间复杂度为O(N3×8)O(N^3 \times 8)O(N3×8)对于N≤50N \le 50N≤50足够高效。实现简洁易于扩展。