题目描述题目要求在一个字母矩阵中查找给定的单词列表。矩阵为l×ll \times ll×l的正方形由大写字母组成。单词可以在水平、垂直或对角线方向上以直线形式出现包括反向即从右向左、从下向上、从右下向左上等。每个单词在矩阵中最多出现一次。对于找到的单词输出其首字母和尾字母的坐标行和列均从111开始计数如果未找到输出Not found。输入格式第一行一个整数lll1≤l≤1001 \le l \le 1001≤l≤100表示矩阵的边长。接下来lll行每行lll个大写字母表示字母矩阵。之后若干行每行一个单词由大写字母组成长度不超过100100100单词数量不超过100100100。输入以一行一个单独的0结束。输出格式对于每个单词输出一行如果找到输出start_row,start_col end_row,end_col其中坐标均为整数用逗号分隔两个坐标对之间用一个空格分隔。如果未找到输出Not found。样例输入5 EDEEE DISKE ESEEE ECEEE EEEEE DISC DISK DISP 0输出2,4 2,2 1,2 4,5 Not found题目分析本题的核心是在二维字母矩阵中搜索单词。由于矩阵规模较小l≤100l \le 100l≤100单词数量不超过100100100可以直接采用枚举起始位置和方向的方法进行搜索。搜索方向单词可以在八个方向上出现水平向右、水平向左、垂直向下、垂直向上、对角线右下、对角线左上、对角线右上、对角线左下。用方向偏移量(Δx,Δy)(\Delta x, \Delta y)(Δx,Δy)表示水平向右(0,1)(0, 1)(0,1)水平向左(0,−1)(0, -1)(0,−1)垂直向下(1,0)(1, 0)(1,0)垂直向上(−1,0)(-1, 0)(−1,0)对角线右下(1,1)(1, 1)(1,1)对角线左上(−1,−1)(-1, -1)(−1,−1)对角线右上(−1,1)(-1, 1)(−1,1)对角线左下(1,−1)(1, -1)(1,−1)搜索策略对于每个单词遍历矩阵中的所有位置作为起始点。如果当前位置的字符与单词的第一个字符匹配则尝试八个方向。对于每个方向检查从起始点开始沿该方向的连续lenlenlen个字符是否与单词完全匹配注意边界检查。如果匹配成功记录起始坐标和结束坐标起始坐标 (len−1)×(Δx,Δy)(len-1) \times (\Delta x, \Delta y)(len−1)×(Δx,Δy)结束搜索。如果所有方向都未匹配则输出Not found。实现细节矩阵索引从111开始便于直接输出坐标。方向偏移量可以使用数组预先定义。注意在检查方向时需要确保整个单词长度不超出矩阵边界。由于每个单词最多出现一次找到后即可跳出所有循环。复杂度分析对于每个单词最多检查l2l^2l2个起始位置和888个方向每个方向最多检查lenlenlen个字符总时间复杂度O(words×l2×8×len)O(\text{words} \times l^2 \times 8 \times \text{len})O(words×l2×8×len)。l≤100l \le 100l≤100len≤100\text{len} \le 100len≤100最坏情况下约100×10000×8×1008×108100 \times 10000 \times 8 \times 100 8 \times 10^8100×10000×8×1008×108可能较大。但实际输入中单词长度和矩阵大小通常较小且匹配失败时可提前终止仍可在限定时间内完成。若需优化可在匹配前先检查边界条件。代码实现// Word-Search Wonder// UVa ID: 422// Verdict: Accepted// Submission Date: 2016-07-17// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn;while(cinn){charmatrix[110][110];for(inti1;in;i)for(intj1;jn;j)cinmatrix[i][j];string word;while(cinword,word!0){boolfoundfalse;intstartx,starty,endx,endy;for(inti1;in;i)for(intj1;jn;j)if(matrix[i][j]word.front()){startxi,startyj;for(intx-1;x1;x)for(inty-1;y1;y){if(x0y0)continue;intnextii,nextjj;boolsametrue;for(intk0;kword.length();k){if(nexti1||nextin||nextj1||nextjn||word[k]!matrix[nexti][nextj]){samefalse;break;}nextix,nextjy;}if(same){endxi(word.length()-1)*x,endyj(word.length()-1)*y;foundtrue;gotoskip;}}}skip:if(found)coutstartx,starty endx,endy\n;elsecoutNot found\n;}}return0;}