[数据结构与算法]洛谷题解-P1101单词方阵

题目概况

题目链接： https://www.luogu.com.cn/problem/P1101
难度： 普及-

题目分析

简化题目： 我觉得题面简洁明了
涉及知识点： 深度优先搜索的玄学操作
解题思路 ：
有几句关键句，我解析一下，大家就基本出思路了：
1. 同一单词摆放时不再改变方向 。也就是说我们不必考虑在dfs中for循环八个方向，只需要在一开始设定好即可
2. 单词与单词之间可以交叉，因此有可能共用字母 换句话说，你最开始必须得八个方向都探一遍，不能探完一个方向就走人
另外，我采用如果当前递归到的某个字符能与前后构成一个单词，则将前后包括自己全部标记为true，在输出时输出非true的方格。

代码拆解及要点解析

普及-大可不必写拆解分析

完整代码

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

int n; //题目设定
char maze[105][105]; //图
bool vis[105][105]; //标记
char link[10]; //衔接下一个的，用于判断
int dir[8][2] = {{0,-1}, {0,1}, {1,0}, {-1,0}, {-1,1}, {-1,-1}, {1,-1}, {1,1}}; //八个方向

//dfs(横坐标，纵坐标，当前字符，当前方向)

bool in(int xx, int yy) {
	return xx >= 1 && xx <= n && yy >= 1 && yy <= n;
} //判断是否越界

bool dfs(int x, int y, char now, int nowdir) { //我在哪里，我是谁，我将去往何处
	//cout << x << " " << y << now << " " << nowdir << endl;
	if (now == 'g') { //如果衔接完了，尘埃落定了
		vis[x][y] = true; //标记当前已经走过
		return true; //开始回去
	}

	int tx = x + dir[nowdir][0]; 
	int ty = y + dir[nowdir][1]; //开始搜索下一个
	if (in(tx, ty)) { 
		if (maze[tx][ty] == link[now]) { //如果我找到了我想要的那个它
			if (dfs(tx, ty, link[now], nowdir)) {
			    vis[x][y] = true; //回来的时候再标记吧
			    return true; //归
		    }
		}
	}
	return false;
}

int main() {
	link['y'] = 'i';
	link['i'] = 'z';
	link['z'] = 'h';
	link['h'] = 'o';
	link['o'] = 'n';
	link['n'] = 'g'; //一个一个预处理衔接
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) { //一定分清i和1的区别，我调了半天
			cin >> maze[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (maze[i][j] == 'y') { //如果是第一个我要的字符
				for (int k = 0; k < 8; k++) { //八个方向都要搜索
					if (dfs(i, j, 'y', k)) { //开始吧
						vis[i][j] = true; //能成标记，不成跳过
					}
				}
			}
		}
	} 
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (vis[i][j]) { //如果是我的选择，就输出原本的样子
				cout << maze[i][j];
			} else { //不是就请屏蔽掉，我不想看
				cout << '*';
			}
		} 
		cout << endl; //换行别忘了，不能挡路
	}
	return 0;
}