(有返回值的DFS(bool 值))
这道题与其他不同的地方在于,搜索一个单词的时候,只能使用一种移动的方式,比如竖直,或者水平,或者斜的,而不可以交叉使用。并且要输出开始位置与结束位置。
遍历每一个点,如果能成功找到,那么这个点就是开始的位置,结束的位置,利用这个单词本身的长度来计算得出,并且需要记录下来是按照哪个方向来移动的,也就是代码中的k
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
int n;
const int MAXN = 100;
char board[MAXN][MAXN];
bool visit[MAXN][MAXN];
string s;
int len = 0;
bool res = false;
int direction[8][2] = {{0,1}, {0,-1}, {1,0}, {-1, 0},{1,1}, {-1,-1}, {1,-1}, {-1,1}};
// 从x,y这个点开始遍历 id表示字符串s当中,前id个字符都相等
bool DFS(int x, int y, int id, int dirs){
if(x < 0 || y < 0 || x>= n || y >= n)
return false;
if(board[x][y] != s[id])
return false;
if(id == len-1)
return true;
return DFS(x+direction[dirs][0], y+direction[dirs][1], id+1, dirs);
}
int main(){
cin>>n;
memset(visit, 0, sizeof(visit));
for(int i = 0; i < n; i++){
for(int j= 0; j < n; j++){
cin>>board[i][j];
}
}
while(cin>>s && s != "0"){
bool res = false;
len = s.length();
int i = 0;
int j = 0;
int k = 0; // 用来记录是哪个方向
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
for(k = 0; k < 8; k++){
res = DFS(i,j,0,k); // 这样每次扩展的时候只专注一个方向
if(res)
break;
}
if(res)
break;
}
if(res)
break;
}
if(!res)
cout<<"Not found"<<endl;
else{
i++;
j++;
int end_i = i+direction[k][0] * (len-1);
int end_j = j+direction[k][1] * (len-1);
printf("%d,%d %d,%d\n", i,j,end_i,end_j);
}
}
return 0;
}