P1101 单词方阵——————暴力或者DFS

落日映苍穹つ 2022-03-27 09:36 212阅读 0赞

# [P1101 单词方阵][P1101] #

## 题目描述 ##

给一n \\times nn×n的字母方阵，内可能蕴含多个“yizhong”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 88 个方向的任一方向，同一单词摆放时不再改变方向，单词与单词之间可以交叉,因此有可能共用字母。输出时，将不是单词的字母用\*代替，以突出显示单词。例如：

输入：
        8                     输出：
        qyizhong              *yizhong
        gydthkjy              gy******
        nwidghji              n*i*****
        orbzsfgz              o**z****
        hhgrhwth              h***h***
        zzzzzozo              z****o**
        iwdfrgng              i*****n*
        yyyygggg              y******g

## 输入输出格式 ##

输入格式：  
第一行输入一个数n。 (7≤n≤100)。

第二行开始输入 n×n的字母矩阵。

输出格式：  
突出显示单词的 n×n矩阵。

输入输出样例  
输入样例\#1：

7
    aaaaaaa
    aaaaaaa
    aaaaaaa
    aaaaaaa
    aaaaaaa
    aaaaaaa
    aaaaaaa

输出样例\#1：

*******
    *******
    *******
    *******
    *******
    *******
    *******

输入样例\#2：

8
    qyizhong
    gydthkjy
    nwidghji
    orbzsfgz
    hhgrhwth
    zzzzzozo
    iwdfrgng
    yyyygggg

输出样例\#2：

*yizhong
    gy******
    n*i*****
    o**z****
    h***h***
    z****o**
    i*****n*
    y******g

--------------------

本来是一个DFS的题，不过暴力做的话，也能够过去，  
因为数据比较小

第一步：找到起点y  
第二步：找八个方向  
第三步：在该方向上判断其它数据是否符合  
第四步：符合的话就将该方向的vis设为1  
回到第一步  
循环直到每个点都作为起点遍历过

## 代码 ##

--------------------

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 107;
    char maze[MAXN][MAXN];
    bool  vis[MAXN][MAXN];
    int dx[] = {
        0, 0, 1, 1, 1, -1,-1,-1};
    int dy[] = {
        1, -1, -1, 0, 1, -1, 0, 1};
    int n;
    char s[10] = "yizhong";
    int cnt = 1;
    int main()
    {
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
    
            memset(vis,0,sizeof(vis));
            cin>>n;
            for(int i=0; i<n; ++i)
                    cin>>maze[i];
            for(int x=0;x<n;++x)
                    for(int y=0;y<n;++y)
                            if(maze[x][y] == 'y')//找起点，
                                    for(int i=0;i<8;i++)//找方向
                                    {
        
                                            int j;
                                            for(j=1;j<7;j++)//按照这个方向依次遍历
                                            {
        
                                                    int nx = x + j*dx[i];
                                                    int ny = y + j*dy[i];
                                                    if(maze[nx][ny]!=s[j])//如果某个数不符合，就排除
                                                            break;
                                            }
                                            if(j==7)
                                                    for(int k=0;k<7;k++)
                                                            vis[x + k*dx[i]][y + k*dy[i]] = 1;
                                    }
            for(int i=0;i<n;++i)
            {
        
                    for(int j=0;j<n;++j)
                            if(vis[i][j])   cout<<maze[i][j];
                            else            cout<<"*";
                    cout<<endl;
            }
            return 0;
    }

[P1101]: https://www.luogu.org/problemnew/show/P1101