• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

洛谷 P1101 单词方阵

开发技术 开发技术 6天前 7次浏览

洛谷P1101 单词方阵

题目描述

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

输入:
8 输出:
qyizhong  *yizhong
gydthkjy  gy******
nwidghji  n*i*****
orbzsfgz  o**z****
hhgrhwth  h***h***
zzzzzozo  z****o**
iwdfrgng  i*****n*
yyyygggg  y******g
输入格式
第一行输入一个数nn。(7 le n le 1007≤n≤100)。

第二行开始输入n times nn×n的字母矩阵。

输出格式
突出显示单词的n times nn×n矩阵。

输入输出样例
输入 #1复制
7
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
输出 #1复制
*******
*******
*******
*******
*******
*******
*******
输入 #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

思路及注意事项

显而易见,本题采用dfs的搜索方式。可以采用种子填充的方式,并用染色的方法去标记矩阵。但是一定要注意,本题中有三个要点:

1.单词朝一个方向排列。

2.不同单词之间具有复用的字母。

3.摆放方向可以有8个方向。

在知晓这三个注意事项以后,就可以开始编码了。

AC代码

#include<iostream>
#include<cstring>
using namespace std;

const static int maxn = 100 + 5;
int n;
char matx[maxn][maxn];
string str = "yizhong";
const int s = 7;
bool judge[maxn][maxn];
int walk[8][2] = { {-1,-1},{0,-1}, {-1,0}, {-1,1}, {1,-1}, {0,1}, {1,0}, {1,1} };

bool inrange(int i, int j) {
	bool flag = true;
	if (i < 0 || i >= n || j < 0 || j >= n) flag = 0;
	return flag;
}

bool dfs(int i,int j,int cnt,int d) {
	if (!inrange(i,j)||matx[i][j] != str[cnt]) return 0;
	if (cnt == s - 1) { judge[i][j] = 1; return 1; }
	int ni = i + walk[d][0];
	int nj = j + walk[d][1];
	if (dfs(ni, nj, cnt + 1, d)) {
		judge[i][j] = 1;
		return 1;
	}
	return 0;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> matx[i];
	}
	memset(judge, 0, sizeof(judge));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (matx[i][j] == 'y') {
				for (int d = 0; d < 8; d++) {
					int ni = i + walk[d][0];
					int nj = j + walk[d][1];
					if (inrange(ni, nj)&&matx[ni][nj]=='i')
					{
						dfs(i, j, 0,d);
					}
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (judge[i][j]) {
				cout << matx[i][j];
			}
			else cout << '*';
		}
		cout << endl;
	}
	return 0;
}

总结与反思

本题一开始由于读题不仔细,做题过程中才意识到字母复用,方向的问题。经过这道题,你一定要认识到,深度优先搜索是具有方向性的,做题时应该留意搜索方向,更重要的是,一定要认真读题。虽然晚上相对来说比较困,但是也需要自己加油努力。

另外,在做题中,尤其是搜索题中,一定要注意边界状态的触发结果,考虑全面,思维一定要清晰

对于本道题,并不需要使用done数组来记录节点是否访问过。因为这道题相当于是单向搜索,关于这一点一定要快速意识到!


程序员灯塔
转载请注明原文链接:洛谷 P1101 单词方阵
喜欢 (0)