题解 P1101 【单词方阵】

CTC050412 · 2018-04-04 22:06:29 · 题解

来先写一下思路：

1.一一枚举开始的位置

2.朝8个方向搜索（其实不如说是递归）

3.在搜索到后标记搜索到了

4.通过标记在搜索完成后再标记哪些地方是“yizhong”

5.输出

严格来说，此题不算是深搜，到不如说是递归，因为只需要往前探路，不需要回溯，下面是代码：

#include<iostream>
#include<cstdio>
using namespace std;
int pd,wx[9] = {0,-1,-1,0,1,1,1,0,-1},wy[9] = {0,0,1,1,1,0,-1,-1,-1},n,b[101][101];
char st[101][101],dc[9] = " yizhong";
void search(int x,int y,int a,int step){
    if(step>7){
        pd = 1;
        return;
    }
    if(st[x][y]!=dc[step]||x<1||x>n||y<1||y>n) return;
    search(x+wx[a],y+wy[a],a,step+1);
    if(pd) b[x][y] = 1; 
}
int main(){
    freopen("testdata.in","r",stdin);
    cin>>n;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++) 
            cin>>st[i][j];
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)
            for(int z = 1;z<=8;z++){
                pd = 0;
                search(i,j,z,1);
            }
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)
            if(!b[i][j]) st[i][j] = '*';
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++)
            cout<<st[i][j];
            cout<<endl;
    }
    return 0;
} 

总而言之，此题不算特别难，觉得不如单词接龙，先比之下，此题就较水了，希望对你有帮助！