UVa 422 Word-Search Wonder

题目描述

题目要求在一个字母矩阵中查找给定的单词列表。矩阵为l×ll \times ll×l的正方形，由大写字母组成。单词可以在水平、垂直或对角线方向上以直线形式出现（包括反向，即从右向左、从下向上、从右下向左上等）。每个单词在矩阵中最多出现一次。对于找到的单词，输出其首字母和尾字母的坐标（行和列均从111开始计数）；如果未找到，输出Not found。

输入格式

第一行一个整数lll（1≤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)

搜索策略

对于每个单词：

1. 遍历矩阵中的所有位置作为起始点。
2. 如果当前位置的字符与单词的第一个字符匹配，则尝试八个方向。
3. 对于每个方向，检查从起始点开始沿该方向的连续lenlenlen个字符是否与单词完全匹配（注意边界检查）。
4. 如果匹配成功，记录起始坐标和结束坐标（起始坐标 +(len−1)×(Δx,Δy)(len-1) \times (\Delta x, \Delta y)(len−1)×(Δx,Δy)），结束搜索。
5. 如果所有方向都未匹配，则输出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≤100，len≤100\text{len} \le 100len≤100，最坏情况下约100×10000×8×100=8×108100 \times 10000 \times 8 \times 100 = 8 \times 10^8100×10000×8×100=8×108，可能较大。但实际输入中单词长度和矩阵大小通常较小，且匹配失败时可提前终止，仍可在限定时间内完成。若需优化，可在匹配前先检查边界条件。

代码实现

// Word-Search Wonder// UVa ID: 422// Verdict: Accepted// Submission Date: 2016-07-17// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn;while(cin>>n){charmatrix[110][110];for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)cin>>matrix[i][j];string word;while(cin>>word,word!="0"){boolfound=false;intstartx,starty,endx,endy;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)if(matrix[i][j]==word.front()){startx=i,starty=j;for(intx=-1;x<=1;x++)for(inty=-1;y<=1;y++){if(x==0&&y==0)continue;intnexti=i,nextj=j;boolsame=true;for(intk=0;k<word.length();k++){if(nexti<1||nexti>n||nextj<1||nextj>n||word[k]!=matrix[nexti][nextj]){same=false;break;}nexti+=x,nextj+=y;}if(same){endx=i+(word.length()-1)*x,endy=j+(word.length()-1)*y;found=true;gotoskip;}}}skip:if(found)cout<<startx<<','<<starty<<' '<<endx<<','<<endy<<'\n';elsecout<<"Not found\n";}}return0;}