本文主要是介绍【洛谷 P1101】单词方阵 题解(深度优先搜索),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
单词方阵
题目描述
给一 n × n n \times n n×n 的字母方阵,内可能蕴含多个 yizhong
单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 8 8 8 个方向的任一方向,同一单词摆放时不再改变方向,单词与单词之间可以交叉,因此有可能共用字母。输出时,将不是单词的字母用 *
代替,以突出显示单词。
输入格式
第一行输入一个数 n n n。 ( 7 ≤ n ≤ 100 ) (7 \le n \le 100) (7≤n≤100)。
第二行开始输入 n × n n \times n n×n 的字母矩阵。
输出格式
突出显示单词的 n × n n \times n n×n 矩阵。
样例 #1
样例输入 #1
7
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
样例输出 #1
*******
*******
*******
*******
*******
*******
*******
样例 #2
样例输入 #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
思路
二维数组 dir
用于表示八个方向的偏移量。
读入 a
方阵的同时初始化 b
方阵为全 *
。
使用三重循环,遍历每一个坐标及其八个方向,并使用深度优先搜索算法搜索,在当前位置 (x, y)
的基础上,根据当前方向 d
和目标单词的下一个字母 p
,判断是否能够继续匹配。如果匹配成功,继续在当前方向上递归查找下一个字母。
在 dfs
函数中,如果成功找到了单词的最后一个字母,将 b
方阵当前位置的字符设为单词的最后一个字母。递归回到上一层dfs
函数时,将 b
方阵当前位置的字符设为 a
方阵对应坐标字母。
注意:同一单词摆放时不再改变方向。
AC代码
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;const int N = 105;
const char *w = "yizhong";
const int dir[8][2] = {{-1, -1},{-1, 0},{-1, 1},{0, -1},{0, 1},{1, -1},{1, 0},{1, 1}};int n;
char a[N][N], b[N][N];bool dfs(int x, int y, int p, int d)
{bool flg = 0;if (w[p] == a[x][y]){if (p == 6){b[x][y] = w[p];return 1;}// cout << x << " " << y << " " << d << " " << a[x][y] << endl;int xx = x + dir[d][0];int yy = y + dir[d][1];if (xx > 0 || xx < n || yy > 0 || yy < n){if (dfs(xx, yy, p + 1, d)){flg = 1;}}}if (flg){b[x][y] = w[p];}return flg;
}int main()
{cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){cin >> a[i][j];b[i][j] = '*';}}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){for (int k = 0; k < 8; k++){dfs(i, j, 0, k);}}}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){putchar(b[i][j]);}putchar('\n');}return 0;
}
这篇关于【洛谷 P1101】单词方阵 题解(深度优先搜索)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!