洛谷 P1101 单词方阵

题目描述

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

输入格式:

第一行输入一个数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特别难。输出不知道哪里就会错。

这里我是用x,y坐标,direction和搜索次数深搜的。

次数到了七次还没有return,说明满足条件,把这七个数变成可视,return掉。

代码

#include <iostream>
using namespace std;
char c[110][110];
char b[7]={'y','i','z','h','o','n','g'};
int s[8]={1,1,1,0,0,-1,-1,-1};
int t[8]={1,0,-1,1,-1,1,0,-1};//s,t是八个方向 
bool show[110][110];//是否显示
void dfs(int x,int y,int dir,int cnt){
    if(cnt==7){//如果dfs次数到了7次,满足。逆推将那些数设为显示
        for(int i=1;i<=7;i++){
            show[x-i*s[dir]][y-i*t[dir]]=1;
        }
        return ;
    }
    if(c[x][y]!=b[cnt]){//如果中间有个数不对应,就return
        return ;
    }
    dfs(x+s[dir],y+t[dir],dir,cnt+1);//下一层
    return ;
}
int main(){
    int n;
    cin>>n;
//全部归零,以免之后初始化错误
    for(int i=0;i<110;i++){
        for(int j=0;j<110;j++){
            c[i][j]='0';
            show[i][j]=0;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>c[i][j];
        }
    }
//每个坐标dfs一次
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<8;k++){
                dfs(i,j,k,0);
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(show[i][j]==1){
                cout<<c[i][j];
            }else{
                cout<<"*";
            }
        }
        cout<<endl;
    }
    return 0;
}

本文链接:https://kaispace.com.cn/index.php/archives/269/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者