【洛谷 P1101】单词方阵 题解（深度优先搜索）

单词方阵

题目描述

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

输入格式

第一行输入一个数 $n$。$(7\le n\le 100)$。

第二行开始输入 $n\times n$ 的字母矩阵。

输出格式

突出显示单词的 $n\times 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;
}