洛谷 P1101 单词方阵

题目链接

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

题目描述

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

输入输出格式

输入格式：

第一行输入一个数nn。(7≤n≤100)。
第二行开始输入n×n的字母矩阵。

输出格式：

突出显示单词的n×n矩阵。

思路

每天一篇博文，嘤嘤嘤，所以我又来啦！
看到一篇题解很牛掰的样子，于是照着就打下来了......qaq
先用数组f，g分别标记x，y的加减，再寻找“y”的位置，找到之我们后用八个方向去试
如果每一位皆符合，那么st字符串数组就赋值，最后处理一下st，输出就好啦

代码

#include<bits/stdc++.h>
using namespace std;
string st[1001],s[1001];
int f[8]={0,-1,-1,-1,0,1,1,1};
int g[8]={1,1,0,-1,-1,-1,0,1};
int a1,a2,n;
bool pd;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)cin>>s[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            st[i]+='0';
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n-1;j++){
            if(s[i][j]=='y'){
                for(int k=0;k<=7;k++){
                    a1=i;a2=j;
                    pd=1;
                    for(int l=1;l<=6;l++){
                        a1+=f[k];a2+=g[k];
                        if(a1<1||a1>n||a2<0||a2>n-1)pd=0;
                        if(pd==0)break;
                        if(l==1&&s[a1][a2]!='i')pd=0;
                        if(l==2&&s[a1][a2]!='z')pd=0;
                        if(l==3&&s[a1][a2]!='h')pd=0;
                        if(l==4&&s[a1][a2]!='o')pd=0;
                        if(l==5&&s[a1][a2]!='n')pd=0;
                        if(l==6&&s[a1][a2]!='g')pd=0;                       
                    }
                    a1=i;a2=j;
                    if(pd){
                        for(int l=0;l<=6;l++){
                            st[a1][a2]=s[a1][a2];
                            a1+=f[k],a2+=g[k];
                        }
                    }
                }
            }
        }
    } 
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n-1;j++){
            if(st[i][j]=='0')st[i][j]='*';
        }
    }
    for(int i=1;i<=n;i++){
        cout<<st[i]<<'\n';
    }
}