搜索 DFS深度优先搜索

洛谷 P1363 幻象迷宫

这种恶魔样例究竟是哪个天才想出来的？！！！！！！

6 20
#.##.##.##.##.##.##.
#.##.##.##.##.##.##.
#.##.##.##.##.##.##.
S.#..#..#..#..#..#..
##..#..#..#..#..#..#
#..#..#..#..#..#..##

md，交了好几发都没过，看了一下这个样例，心都凉了。

能想出来这题解的更是天才Orz，

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1500 + 5;
const int dx[6] = {0, 1, -1, 0, 0};
const int dy[6] = {0, 0, 0, 1, -1};

int n, m;
int st_x, st_y;
int vis[MAXN][MAXN][3];
bool fl, a[MAXN][MAXN];
char ch;
//x和y是取过模的坐标，lx和ly是没有取模的坐标
//简单来说就是开两个图，一个无穷大，但坐标映射的和原图一样大的区域内，另一个和原图一样大，只要从某个点出发又走到了这个点，那就显然是可以走无限远的
void dfs(int x, int y, int lx, int ly){
	if(fl) return;
    //如果原图上面走过 并且在无穷大图上面走到了和原图一样位置的点且不是同一次
	if(vis[x][y][0] && (vis[x][y][1] != lx || vis[x][y][2] != ly)){
		fl = 1; return;//标记为能够走无限远
	}
    //将新走到的横纵坐标映射到原图的位置的横纵坐标进行更新 同时将原图上的这点标记为走过
	vis[x][y][1] = lx, vis[x][y][2] = ly, vis[x][y][0] = 1;
    //上下左右走
	for(int i = 1; i <= 4; ++i){
		int xx = (x + dx[i] + n) % n;
		int yy = (y + dy[i] + m) % m;
		int lxx = lx + dx[i], lyy = ly + dy[i];//计算走到点的坐标
        //如果这个地方可以走（不是障碍物）
		if(!a[xx][yy]){
            //如果新到达的点映射在原图上的坐标不同 || 原图没有走过
			if(vis[xx][yy][1] != lxx || vis[xx][yy][2] != lyy || !vis[xx][yy][0]){
				dfs(xx, yy, lxx, lyy);
			}
		}
	}
}
int main(){
	while(cin >> n >> m){
		fl = 0;
		memset(a, 0, sizeof a);
		memset(vis, 0, sizeof vis);
		for(int i = 0; i < n; ++i){
			for(int j = 0; j < m; ++j){
				cin >> ch;
				if(ch == '#') a[i][j] = 1;
				if(ch == 'S') st_x = i, st_y = j;
			}
		}
		dfs(st_x, st_y, st_x, st_y);
		if(fl) puts("Yes");
		else puts("No");
	}
	return 0;
}