P1101 单词方阵【DFS】
https://www.luogu.com.cn/problem/P1101
题目描述
给一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;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-10-02，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
