【题目来源】
洛谷：P1101 单词方阵 - 洛谷
【题目描述】
给一 \(n\times n\) 的字母方阵，内可能蕴含多个 yizhong 单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 \(8\) 个方向的任一方向，同一单词摆放时不再改变方向，单词与单词之间可以交叉，因此有可能共用字母。输出时，将不是单词的字母用 * 代替，以突出显示单词。
【输入】
第一行输入一个数 \(n\)。\((7\le n\le 100)\)。
第二行开始输入 \(n\times n\) 的字母矩阵。
【输出】
突出显示单词的 \(n\times n\) 矩阵。
【输入样例】
8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg
【输出样例】
*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g
【解题思路】
【算法标签】
《洛谷 P1101 单词方阵》 #字符串# #搜索#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n; // 矩阵大小
int mark[110][110]; // 标记数组，记录需要输出的字符位置
char fz[110][110]; // 存储输入的字符矩阵
string yz = "yizhong"; // 目标字符串
// 8个方向的方向数组：上、左上、左、左下、下、右下、右、右上
int dx[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};/*** 在(x,y)位置搜索目标字符串* @param x 当前行坐标* @param y 当前列坐标*/
void search(int x, int y)
{// 遍历8个方向for (int i = 0; i < 8; i++) {int tx, ty, m = 1; // tx,ty: 临时坐标, m: 匹配标志// 检查当前方向是否能匹配完整字符串for (int j = 0; j < yz.size(); j++) {tx = dx[i] * j + x;ty = dy[i] * j + y;// 如果超出边界或字符不匹配，标记为不匹配if (fz[tx][ty] != yz[j]) {m = 0;break;}}// 如果不匹配则跳过if (m == 0) {continue;}// 匹配成功，标记所有匹配位置for (int j = 0; j < yz.size(); j++) {mark[dx[i] * j + x][dy[i] * j + y] = 1;}}
}int main()
{// 输入矩阵大小cin >> n;// 输入字符矩阵for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cin >> fz[i][j];}}// 遍历矩阵每个位置进行搜索for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {search(i, j);}}// 输出结果：匹配位置显示原字符，其他位置显示*for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (mark[i][j] == 1) {cout << fz[i][j];}else {cout << "*";}}cout << endl;}return 0;
}
【运行结果】
8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg
*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g