一道dfs题目
P1101单词方阵
开通博客的第二天！
好啦今天来写一下P1101单词方阵的题解，这是一道平平无奇的深搜题目。
主要思路
遍历整个方阵，如果找到'y'就开始搜，如果第d次搜索搜到的是目标字符串中的第d个字符，那就继续搜，否则return。
在一次搜索中，搜索的方向是固定的，不能拐弯，所以，递归的时候只能递归一种方向。因此，八个方向要在主程序里面循环。
定义变量
string tgt=" yizhong";
int n;
int dx[9]={0,1,1,1,-1,-1,-1,0,0};
int dy[9]={0,0,1,-1,0,1,-1,1,-1};
char word[105][105];
bool gone[105][105];
int ans[105][3];
bool anst[105][105];tgt是目标字符串，前面加空格是为了下标从1开始，便于理解；n是边长；dx和dy是二元组，用来控制方向；word存单词方阵；gone检测该位置有没有走过；ans存之前找到的下标；anst是我们输出的答案。
dfs
void dfs(int d,int x,int y,int way)//d是深度，x是x坐标，y是y坐标，way是方向，由于不能拐弯，所以一个dfs里搜索的方向是一致的
{
if((x>0&&x<=n&&y>0&&y<=n)==false||gone[x][y]==true||word[x][y]!=tgt[d])//递归出口，如果越界或者走过或者该位置字符不在tgt内。
{
return;
}
gone[x][y]=true;//标记为走过
ans[d][1]=x;//把x坐标存进数组
ans[d][2]=y;//把y坐标存进数组
if(d==7)//如果找到了目标字符串
{
for(int i=1;i<=7;i++)//把这条路径标记为true
{
anst[ans[i][1]][ans[i][2]]=true;
}
return;
}
dfs(d+1,x+dx[way],y+dy[way],way);//递归，按照相同的方向搜索
}AC代码
#include<bits/stdc++.h>//万能头
using namespace std;
string tgt=" yizhong";//变量定义在上面已经说明过，这里不再赘述
int n;
int dx[9]={0,1,1,1,-1,-1,-1,0,0};
int dy[9]={0,0,1,-1,0,1,-1,1,-1};
char word[105][105];
bool gone[105][105];
int ans[105][3];
bool anst[105][105];
void dfs(int d,int x,int y,int way)//d是深度，x是x坐标，y是y坐标，way是方向，由于不能拐弯，所以一个dfs里搜索的方向是一致的
{
if((x>0&&x<=n&&y>0&&y<=n)==false||gone[x][y]==true||word[x][y]!=tgt[d])//递归出口，如果越界或者走过或者该位置字符不在tgt内。
{
return;
}
gone[x][y]=true;//标记为走过
ans[d][1]=x;//把x坐标存进数组
ans[d][2]=y;//把y坐标存进数组
if(d==7)//如果找到了目标字符串
{
for(int i=1;i<=7;i++)//把这条路径标记为true
{
anst[ans[i][1]][ans[i][2]]=true;
}
return;
}
dfs(d+1,x+dx[way],y+dy[way],way);//递归，按照相同的方向搜索
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>word[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(word[i][j]=='y')//找到了y起点，开始搜
{
for(int k=1;k<=8;k++)//遍历8个方向
{
memset(gone,false,sizeof(gone));//先把判重数组清零，以免少搜。
dfs(1,i,j,k);//按照第k个方向深搜
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(anst[i][j]==true)//如果为真，说明是目标字符串，输出原字符
{
cout<<word[i][j];
}
else//否则输出'*'
{
cout<<'*';
}
}
cout<<endl;
}
return 0;
}