题解 P1101 【单词方阵】

· · 题解

深度优先搜索

思路：

先找y，如果找到y了就说明它附近可能会有我们要找的单词 yizhong 
于是接下来沿着8个方向找izhong， 如果越界或者不符合就舍弃， 如果找到了就记录在ans数组里面，
最后输出ans数组

代码简化技巧

1. 方向数组的运用

const int dx[] = {1, 1, 1, 0, 0, -1,-1,-1 };  
const int dy[] = {1, 0,-1, 1,-1, 0 , 1,-1 };

2. 定义常量比较数组

const string cmp = "yizhong";

这样判断是否有izhong的时候就比较方便 可以用一个for循环，比如，x行y列有个“y”，以第i个方向为例：

for(int j = 1;j <= 6;j++) { //以1个方向比较 “izhong”   
            int nx = x + j*dx[i];    
            int ny = y + j*dy[i];
            if(nx < 1 || nx > n || ny < 1 || ny > n) { //判越界 
                flag = 0;
                break;
            }
            if(cmp[j] != A[nx][ny]) {  
                flag = 0;
                break;
            }
        }

这里j是步长，这里的j正好对应了yizhong 的第j位 所以正好可以对应起来

完整代码：

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 110;
const int dx[] = {1, 1, 1, 0, 0, -1,-1,-1 };  //方向数组 
const int dy[] = {1, 0,-1, 1,-1, 0 , 1,-1 };
const string cmp = "yizhong"; // 比较数组 

char A[maxn][maxn], ans[maxn][maxn];
int mark[maxn][maxn], n;

void dfs(int x,int y) {
    for(int i = 0;i < 8;i++) {  //枚举8个方向 
        int flag = 1;
        for(int j = 1;j <= 6;j++) { //以1个方向比较 “izhong”   
            int nx = x + j*dx[i];    
            int ny = y + j*dy[i];
            if(nx < 1 || nx > n || ny < 1 || ny > n) { //判越界 
                flag = 0;
                break;
            }
            if(cmp[j] != A[nx][ny]) {  //判断第j位是否符合 
                flag = 0;
                break;
            }
        }
        if(flag == 0) continue;
        for(int j = 0;j <= 6;j++) { //符合就记录在ans数组里 
            int nx = x + j*dx[i];
            int ny = y + j*dy[i];
            ans[nx][ny] = A[nx][ny];
        }
    }
    return;
}

int main() {
    cin >> n;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) {
            cin >> A[i][j];
        }
    }

    for(int i = 1;i <= n;i++) { 
        for(int j = 1;j <= n;j++) {
            if(A[i][j] == 'y') dfs(i,j);//如果发现有y就开始搜索 
        }
    }
    for(int i = 1;i <= n;i++) { //输出 
        for(int j = 1;j <= n;j++) {
            if(ans[i][j] == 0) ans[i][j] = '*';//如果没有改动就输出* 
            cout << ans[i][j];
        }
        cout << endl;
    }
    return 0;
}