526互联

【LuoGu 1363】幻象迷宫——深度优先搜索 + 读题

发布时间 2023-08-20 11:19:01作者: 天涯海角寻天涯

幻象迷宫

题目背景

（喵星人 LHX 和 WD 同心协力击退了汪星人的入侵，不幸的是，汪星人撤退之前给它们制造了一片幻象迷宫。）

WD：呜呜，肿么办啊……

LHX：momo...我们一定能走出去的！

WD：嗯，+U+U！

题目描述

幻象迷宫可以认为是无限大的，不过它由若干个 \(N\times M\) 的矩阵重复组成。矩阵中有的地方是道路，用 \(\verb!.!\) 表示；有的地方是墙，用 \(\verb!#!\) 表示。LHX 和 WD 所在的位置用 \(\verb!S!\) 表示。也就是对于迷宫中的一个点\((x,y)\)，如果 \((x \bmod n,y \bmod m)\) 是 \(\verb!.!\) 或者 \(\verb!S!\)，那么这个地方是道路；如果 \((x \bmod n,y \bmod m)\) 是\(\verb!#!\)，那么这个地方是墙。LHX 和 WD 可以向上下左右四个方向移动，当然不能移动到墙上。

请你告诉 LHX 和 WD，它们能否走出幻象迷宫（如果它们能走到距离起点无限远处，就认为能走出去）。如果不能的话，LHX 就只好启动城堡的毁灭程序了……当然不到万不得已，他不想这么做。

输入格式

输入包含多组数据，以 EOF 结尾。

每组数据的第一行是两个整数 \(N,M\)。

接下来是一个 \(N\times M\) 的字符矩阵，表示迷宫里 \((0,0)\) 到 \((n-1,m-1)\) 这个矩阵单元。

输出格式

对于每组数据，输出一个字符串，Yes 或者 No。

样例 #1

样例输入 #1

5 4
##.#
##S#
#..#
#.##
#..#
5 4
##.#
##S#
#..#
..#.
#.##

样例输出 #1

Yes
No

提示

  • 对于 \(30\%\) 的数据，\(1\le N,M\le 20\)；
  • 对于 \(50\%\) 的数据，\(1\le N,M\le 100\)；
  • 对于 \(100\%\) 的数据，\(1\le N,M\le 1500\)，每个测试点不超过 \(10\) 组数据。

解法

看到这种迷宫类型的题目很容易想到\(DFS\)。但这题的要求又与常规的\(DFS\)题不一样，它要求判断能够从起点只向上、下、左、右四个方向前进能不能走到无穷远处。
所以，问题的关键在于如何判断能否走到无穷远处？
假设存在一条路径，能够通向无穷远处。由于迷宫是不断重复的，因此对于路径上的一个点\((x, y)\)，一定能走到扩展出来的迷宫中其对应的位置\((x \,mod \,n,\,y\,mod \,m)\)。因此解决方案就呼之欲出:对坐标取模, \(\forall x \in [0, n - 1], \, y \in [0, m - 1]\)，开一个三维数组\(s[x][y][3]\)，其中\(s[x][y][0]\)表示\((x,y)\)是否已经访问过一次, \(st[x][y][1], st[x][y][2]\)记录上一次走到\((x, y)\)的实际坐标\((x^{'}, y^{'})\)。设当前实际坐标为\((x^{''}, y^{''})\)。如果\(x^{''} \neq x^{'} || y^{''} \neq y^{'}\)，且\(st[x][y][0] == true\)，则说明从一个矩阵中的某一个位置可以走到扩展出来的迷宫中的对应位置。不断重复这个过程，可以一直向外走，因此这种情况就是能够走到无穷远处的地方。
注：一定要排除走回原来位置的情况，这样只是在一个矩阵内绕圈，不算走到无穷远处。

#include<bits/stdc++.h>

const int N = 1573;

int n, m;
std::vector<std::string> g(N);
int st[N][N][3];
bool flag;

const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, 1, -1, 0}; 

void dfs(int x, int y, int lx, int ly) {
	if(flag) return;
	if(st[x][y][0] && (st[x][y][1] != lx || st[x][y][2] != ly)) {
		flag = true;
		return;
	}
	st[x][y][0] = true;
	st[x][y][1] = lx;
	st[x][y][2] = ly;
	for(int i = 0; i < 4; i ++ ) {
		int lxx = lx + dx[i];
		int lyy = ly + dy[i];
		int nx = (x + dx[i] + n) % n;
		int ny = (y + dy[i] + m) % m;
		if(g[nx][ny] != '#' && (st[nx][ny][1] != lxx || st[nx][ny][2] != lyy || !st[nx][ny][0])){
			dfs(nx, ny, lxx, lyy);
		}
	}
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	while(std::cin >> n >> m) {
		memset(st, 0, sizeof st);
		flag = false;
		int sx = -1, sy = -1;
		for(int i = 0; i < n; i ++ ) {
			std::cin >> g[i];
		}

		for(int i = 0; i < n; i ++ ) {
			for(int j = 0; j < m; j ++ ) {
				if(g[i][j] == 'S'){
					sx = i;
					sy = j;
					break;
				}
			}
			if(sx >= 0 && sy >= 0) break;
		}
		dfs(sx, sy, sx, sy);
		
		if(flag) std::cout << "Yes" << '\n';
		else std::cout << "No" << '\n';
	}

	return 0;
}