题解 P1101 【单词方阵】

· · 题解

本大牛蒟蒻第一次发题解，如有不足，还请见谅！

进入正题。看到题解里大部分dalao都用的是DFS，于是我也采用了DFS搜索（本蒟蒻暂时想不出其他方法了）。
看懂了题其实发现挺简单，只要找到‘y’就向四周八个方向搜，搜出一个就保存坐标，之后输出就行。

下面送上你们最喜爱的完整代码：

#include<bits/stdc++.h>//万能头文件，不用我多介绍了
using namespace std;
struct node{int zx,zy;};
vector<node> k;//定义一个类型为node的动态数组，用来保存坐标
int n,f[101][101],xy[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};//定义标记用的f数组，以及方向二维数组
char a[101][101],h[101][101];//a为输入用的数组，h为输出用的数组
string s="yizhong";//定义为“yizhong”的字符串
void dfs(int x,int y,int ans,int num){第一，二个参数为坐标，第三个为现在的字符在字符串中的下标，第四个方向
    if(ans==7){//如果搜到第七个字符，就标记h数组
        for(int i=0;i<=6;i++){
            int kx=k[i].zx,ky=k[i].zy;//为之前动态数组保存的坐标
            h[kx][ky]=s[i];//坐标与字符一一对应
        }
        return;
    }
    for(int i=0;i<=7;i++){
        int tx=x+xy[i][0],ty=y+xy[i][1];
        if(ans>1&&i!=num) continue;//如果方向不一就重新循环
        if(tx<1||tx>n||ty<1||ty>n) continue;//防止越界
        if(a[tx][ty]!=s[ans]) continue;//判断字符是否正确
        if(f[tx][ty]==0){//如果没搜过就搜索
            f[tx][ty]=1;//标记为搜过
            k.push_back(node{tx,ty});//保存坐标
            dfs(tx,ty,ans+1,i);//第四个参数为方向
            k.pop_back();//一定记得弹出
            f[tx][ty]=0;//回溯
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)//输入
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            h[i][j]='*';//先将h数组都标记为‘*’
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(a[i][j]=='y'){//搜到‘y‘就搜索
                k.push_back(node{i,j});//一定要保存‘y’坐标
                dfs(i,j,1,0);//第三个参数一定要为1，从‘i’开始搜
                k.pop_back();
            }
        }
    for(int i=1;i<=n;i++){//输出
        for(int j=1;j<=n;j++)
            cout<<h[i][j];
        cout<<endl;
    }
    return 0;
}
（自我感觉解释得很清楚）

看我码字码得这么辛苦，不点个赞再走吗？