给一n×n的字母方阵，内可能蕴含多个“yizhong”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 8个方向的任一方向，同一单词摆放时不再改变方向，单词与单词之间可以交叉,因此有可能共用字母。输出时，将不是单词的字母用*代替，以突出显示单词。例如：
输入： 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
输出样例：
*******
*******
*******
*******
*******
*******
*******
输入样例2：
8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg
输出样例：
*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g
提供两种解法 一种是dfs 一种是暴力 要是只想把这个题ac掉的话直接往下看暴力法就好了 想练一练dfs的可以好好看看解法一
解法一（dfs）：
#include<bits/stdc++.h> using namespace std; char m[105][105],a[]="yizhong",ans[105][105]; int n,f[2][8]={1,1,1,0,0,-1,-1,-1,1,0,-1,1,-1,1,0,-1}; void dfs(int x,int y,int k,int p) //x y 为当前坐标 k代表朝哪个方向搜 p代表是这个方向上的第几个字母 { int i; if(p==6) { for(i=p;i>=0;i--) ans[x-i*f[0][k]][y-i*f[1][k]]=a[6-i]; //我用ans数组保存要输出的“地图”，如果有符合的字符串就记录到ans里 return; } else if(m[x+f[0][k]][y+f[1][k]]==a[p+1]) dfs(x+f[0][k],y+f[1][k],k,p+1); //沿着k方向搜 由于不会转向别的方向 所以不需要vis数组判断是否已经经过这个点 这是和其他的dfs区别最大的地方 else return; } int main() { int i,j,k; cin>>n; for(i=0;i<n;i++) cin>>m[i]; for(i=0;i<n;i++) for(j=0;j<n;j++) ans[i][j]='*'; //对ans数组初始化 全部设为“*” for(i=0;i<n;i++) for(j=0;j<n;j++) { if(m[i][j]=='y') for(k=0;k<8;k++) { dfs(i,j,k,0); } } for(i=0;i<n;i++) { for(j=0;j<n;j++) cout<<ans[i][j]; cout<<endl; } }
解法二（暴力）：
#include<iostream> #include<cstdio> using namespace std; string s[111],ans[111]; const int a[8]={0,-1,-1,-1,0,1,1,1},b[8]={1,1,0,-1,-1,-1,0,1}; int t1,t2,kk,k,i,j,n; bool bb; int main() { cin>>n; for (i=1; i<=n; i++) cin>>s[i]; for (i=1; i<=n; i++) for (j=1; j<=n; j++) ans[i]+='0'; for (i=1; i<=n; i++) for (j=0; j<=n-1; j++) if (s[i][j]=='y') { for (k=0; k<=7; k++) { t1=i; t2=j; bb=1; for (kk=1; kk<=6; kk++) { t1+=a[k]; t2+=b[k]; if (t1<1||t1>n||t2<0||t2>n-1) bb=0; if (bb==0) break; if (kk==1&&s[t1][t2]!='i') bb=0; if (kk==2&&s[t1][t2]!='z') bb=0; if (kk==3&&s[t1][t2]!='h') bb=0; if (kk==4&&s[t1][t2]!='o') bb=0; if (kk==5&&s[t1][t2]!='n') bb=0; if (kk==6&&s[t1][t2]!='g') bb=0; } t1=i; t2=j; if (bb) for (kk=0; kk<=6; kk++) ans[t1][t2]=s[t1][t2],t1+=a[k],t2+=b[k]; } } for (i=1; i<=n; i++) for (j=0; j<=n-1; j++) if (ans[i][j]=='0') ans[i][j]='*'; for (i=1; i<=n; i++) cout<<ans[i]<<endl; return 0; }
解法二是别人的题解 直接拿来用了 可以更优化一点的 不过没必要了 都可以ac