单词方阵（含代码详解）

单词方阵

题目描述

给一 $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

题目来源

洛谷

题解

#include <bits/stdc++.h>
using namespace std;const int maxn = 100 + 10; // 定义最大矩阵的大小，给数组留出足够的空间struct node {int x, y; // 用于记录某个字母在矩阵中的坐标
} c[maxn]; // 定义一个 node 类型的数组，用来存储匹配到的“yizhong”单词的路径char fz[maxn][maxn]; // 保存字母矩阵
char stand[] = "yizhong"; // 保存要查找的单词 "yizhong"，用于匹配int vis[maxn][maxn]; // 保存路径信息，用于标记该位置是否是“yizhong”单词的一部分// 定义 8 个方向的位移数组，分别表示上左、上、上右、左、右、下左、下、下右
int dir[][2] = {{-1, -1}, {-1, 0}, {-1, 1},{0, -1},         {0, 1},{1, -1}, {1, 0}, {1, 1}
};void dfs(int x, int y, node c[], int k, int cur) {// 如果已经匹配到 "yizhong" 的最后一个字母if (cur == 7) {// 标记路径上所有字符为单词的一部分for (int i = 0; i < 7; i++) {vis[c[i].x][c[i].y] = 1;}} else {// 沿着正确的方向 k 继续搜索下一个字符int dx = x + dir[k][0];int dy = y + dir[k][1];// 如果当前匹配到第 6 个字符，或者下一个字符匹配 "yizhong" 的下一个字母if (cur == 6 || fz[dx][dy] == stand[cur + 1]) {c[cur].x = x; // 记录当前字符的位置c[cur].y = y;dfs(dx, dy, c, k, cur + 1); // 递归搜索下一个字符}}
}int main() {int n;scanf("%d", &n); // 读取矩阵大小for (int i = 0; i < n; i++) {scanf("%s", fz[i]); // 读取字母矩阵}memset(vis, 0, sizeof(vis)); // 将标记数组初始化为 0// 遍历矩阵中的每个位置for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {// 如果找到 "y" 字符if (fz[i][j] == 'y') {// 尝试从该位置出发，沿着 8 个方向之一寻找 "yizhong"for (int k = 0; k < 8; k++) {int x = i + dir[k][0];int y = j + dir[k][1];// 如果下一个字符是 "i"，继续深度优先搜索if (fz[x][y] == 'i') {dfs(i, j, c, k, 0);}}}}}// 输出结果矩阵，将不是单词的字母替换为 "*"for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (vis[i][j]) {printf("%c", fz[i][j]); // 输出属于单词的一部分的字符} else {printf("*"); // 输出 "*" 替换不属于单词的字符}}printf("\n"); // 换行}return 0; // 程序结束
}