ACM 训练日志记录 · 思考 · 成长
提交 / 修改记录
廖夏 / 题目列表训练档案
导出

P1101　单词方阵

来源：洛谷 ★ 1000

模拟字符串搜索枚举仍在学习
本题活力0.48按难度、完成结果与训练证据估算

算法如山行则将至

查看原题廖夏 的主页

题目描述

单词方阵

题目描述

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

输入格式

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

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

输出格式

突出显示单词的 $n \times n$ 矩阵。

样例 1

输入：

7
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa

输出：

*******
*******
*******
*******
*******
*******
*******

样例 2

输入：

8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg

输出：

*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g

代码

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int MAXN = 105;
int n;
bool cnt[MAXN][MAXN];
char a[MAXN][MAXN];
int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy[] = {1, -1, 0, 1, -1, 0, 1, -1};
string word = "yizhong";
int main(){
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> a[i][j];
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			// 下面枚举八个方向
			if (a[i][j] != 'y') continue;
			for (int k = 0; k < 8; k++){
				int x = i, y = j;
				bool flag = true;
				for (int m = 1; m < word.length(); m++){
					x += dx[k]; y += dy[k];	
					if (a[x][y] != word[m]) {flag = false; break;} 
				}
				if (flag){
					x = i, y = j;
					cnt[x][y] = 1;
					for (int m = 1; m < word.length(); m++){
						x += dx[k]; y += dy[k];	
						cnt[x][y] = 1;
					}
				}
			}
		}
	}
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			if (cnt[i][j]) cout << a[i][j];
			else cout << "*";
		}
		cout << "\n";
	}
	return 0;
}