洛谷题单指南-搜索-P1101 单词方阵

原题链接：https://www.luogu.com.cn/problem/P1101

题意解读：对于方阵中的每一个字符，在8个方向上判断是否和"yizhong"匹配，是一个递归问题。

解题思路：

用char a[N][N]存储所有字符方阵，用bool b[N][N]标记每个字符是否在任一方向上和yizhong匹配

遍历方阵每一字符，如果是'y'

则在8个方向上递归判断是否和"yizhong"匹配

如果匹配，更新每一个位置的b[i][j]=true

注意只要b[i][j]被更新为true，证明总在某一方向能匹配，如果后续遍历到该位置某个方向不匹配，也不能再重新更新为false

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 105;

const string YZ = "yizhong";
char a[N][N]; //字符数组
bool b[N][N]; //标记字符是否在任意方向上匹配上yizhong
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int n;

//从x,y开始，比较第idx个字符，方向为dir
bool dfs(int x, int y, int idx, int dir)
{
    if(idx == 6 && a[x][y] == YZ[idx])
    {
        return true; //如果比较到最后一个字符，说明该方向匹配
    } 

    if(a[x][y] != YZ[idx]) return false; //如果遇到不相等的字符，说明该方向不匹配

    int nx = x + dx[dir], ny = y + dy[dir];
    if(nx >= 1 && nx <= n && ny >= 1 && ny <= n)
    {
        bool res = dfs(nx ,ny, idx + 1, dir);
        if(res) b[nx][ny] = res; //如果匹配上，才更新标记，不能把之前匹配过的覆盖掉
        return res;
    }

    return false;
}

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] == YZ[0])
            {
                for(int k = 0; k < 8; k++)
                {
                    bool res = dfs(i, j, 0, k); //只要有一个方向匹配，就要保留匹配的状态
                    if(res) b[i][j] = res;
                }    
            }
        }
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(b[i][j]) cout << a[i][j];
            else cout << "*";
        }
        cout << endl;
    }
}