给一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
第一行输入一个数nn。(7 \le n \le 1007≤n≤100)。
第二行开始输入n \times nn×n的字母矩阵。
突出显示单词的n \times nn×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
题解:判断某一个点是否为"yizhong"的开始,即判断是否为'y',这时候可以直接向八个方向进行DFS。也可以继续判断这八个方向中,下一个字符是'i'的是那个,那么就按这个方向DFS。
在DFS时需要注意,当前遍历的"yizhong"的路径如何保存,这里通过一个path[ ] 来保存,如果最后遍历到 'g' ,即当我们的遍历cnt==7时,那就将 path[ ] 里面的坐标标记成1,代表这些是符合要求的。
1、如果还未到7次,说明当前还需要继续DFS,一种是当下一个字符与之相匹配时,这时,cnt+ 1,继续按该方向遍历。
2、当我们遍历到cnt == 6 时,就已经遍历完字符串了,这时候需要我们保存下来路径,就是又进行了DFS,但是并没有将下一个存到vis里面。
3、也可以调整一下下面的代码顺序,不再递归cnt==6这一次。
自己写的很难看,看了题解之后重新写了一遍。
#include <stdio.h>
#include <string.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[200][200];
char parent[] = "yizhong";
int vis[200][200];
struct node {
int x,y;
}path[10];
int dx[] = {1,1,1,0,0,-1,-1,-1};
int dy[] = {0,1,-1,1,-1,0,1,-1};
void dfs(int x,int y,int cnt, int k){
if(cnt == 7){
for(int i = 0; i < 7; i ++){
vis[path[i].x][path[i].y] = 1;
}
}
else {
int tx = x + dx[k];
int ty = y + dy[k];
if(cnt == 6 || s[tx][ty] == parent[cnt+1]){
path[cnt].x = x;
path[cnt].y = y;
dfs(tx,ty,cnt+1,k);
}
}
}
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i ++)
{
cin >> s[i];
}
memset(vis,0,sizeof(vis));
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++)
{
if(s[i][j] == 'y'){
for(int k = 0; k < 8; k ++){
int ti = i + dx[k];
int tj = j + dy[k];
if(s[ti][tj] == 'i'){
dfs(i,j,0,k);
}
}
}
}
}
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < n; j ++)
{
if(vis[i][j]) cout << s[i][j];
else cout << '*' ;
}
cout << endl;
}
return 0;
}