P1101 单词方阵

NOI

 2019/06/17 

dir 这个数组是很好用的，不需要为8个方向特意写8个不同的函数，只需要写一个函数但是改变取哪一个dir[i]来判定哪一个方向符合条件就行了

#include<iostream>
#include<cstdio>
using namespace std;
char matrix[103][103], yizhong[8]="yizhong"; bool mark[103][103];
/// matrix 存储每个位置的字母，yizhong 存储我们要找的字符串 "yizhong"，mark存储这个位置符不符合要求，最后要不要被变成 "*" 输出
int dir[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
/// dir[8] 存储了8个方向，dir[i][0] 是x轴坐标，dir[i][1] 是y轴坐标
void dfs(int,int); /// 这个题虽然放在dfs里面但是因为这个字符串的方向是固定的，不会拐弯抹角，所以好像和dfs没什么关系
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>matrix[i][j];

    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dfs(i,j);

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

    return 0;
}
void dfs(int x, int y)
{
    for(int i=0;i<8;i++){ ///对于任意一个点，我们都看看它周围八个方向各自符不符合条件
        int j=0;bool flag=true;
        while(j<7){ ///分别检视每一个字符 与 yizhong 是否匹配
            if(matrix[x+j*dir[i][0]][y+j*dir[i][1]] != yizhong[j]){ ///非常精髓
                flag=false; break; /// 不匹配，flag=false
            }
            j++;
        }
        if(flag){ ///匹配的话就记录下来它们是符合要求的，最后直接输出当前位置的字符
            for(int j=0;j<7;j++)
                mark[x+j*dir[i][0]][y+j*dir[i][1]]=true;
        }
    }
}

Author：Yao Lirong

Link：https://yao-lirong.github.io/blog/P1101%20%E5%8D%95%E8%AF%8D%E6%96%B9%E9%98%B5/

Publish date：June 17th 2019, 12:00:00 am

Update date：June 27th 2019, 8:38:12 pm

License：本文采用 Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) 进行许可

Next Post

P1019 单词接龙
Previous Post

P1219 八皇后

CATALOG