洛谷题单指南-图的基本应用-P1363 幻象迷宫

原题链接：

题意解读：迷宫可以无限扩展，对第一个样例进行模拟，扩展4块的示意图：

从起点S，沿着红色虚线，是可以无限走下去的，要判断是否能够无限走下去。

解题思路：

直观上，会考虑把迷宫复制多块，但是会面临2个问题：

1、内存可能爆掉

2、如何有效判断可以无限走下去？只考虑竖向或者横向连通是不够的，比如以下case：

横向上并没有连通，借道扩展出来的迷宫才可抵达。

所以，不必把迷宫复制多块，直接计算坐标x = rx % n， y = ry % m来DFS，同时保留真实坐标rx，ry，同样面临两个问题：

1、如何标记一个点是否走过，以及如何保存走过时的真实x、y坐标

可以用二维数组bool vis[N][M]，vis[x][y] = true表示一个点已经走过，x、y是对n、m取模之后的坐标

用另外两个二维数组int rrx[N][M], ry[N][M]，rrx[x][y] = rx记录x、y对应的真实x坐标，rry[x][y] = ry记录x、y对应的真实y坐标

判断一个点能不能再走的条件：!vis[x][y] || rrx[x][y] != rx || rry[x][y] != ry

也就是只要一个点未标记过，或者真实x坐标不同、或者真实y坐标不同，任意一个成立则说明该点可以走。

2、如何判断可以无限走下去

可以断定，如果一个坐标点，如果两次都走到过（取模后的坐标一致），并且真实坐标不相同，则一定可以无限走下去。

两次都走到过的判断：vis[x][y] && rrx[x][y] == rx && rry[x][y] == ry

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1505, M = 1505;

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

char a[N][M];
int n, m, x, y;
bool vis[N][M];
int rrx[N][M], rry[N][M];

//x,y是对n，m取模后的坐标，rx，ry是真实坐标
bool dfs(int x, int y, int rx, int ry)
{
    //如果两次走到同一个位置的点，且真实坐标不同，则说明可以无限走下去
    if(vis[x][y] && (rx != rrx[x][y] || ry != rry[x][y]))
    {
        return true;
    }
    //做标记，并记录真实坐标
    vis[x][y] = true; rrx[x][y] = rx; rry[x][y] = ry;

    for(int i = 0; i < 4; i++)
    {
        int nx = (x + dx[i] + n) % n; //+n防止为负
        int ny = (y + dy[i] + m) % m; //+m防止为负
        int nrx = rx + dx[i];
        int nry = ry + dy[i];
        if(a[nx][ny] == '#') continue;
        if(vis[nx][ny] && nrx == rrx[nx][ny] && nry == rry[nx][ny]) continue;
        if(dfs(nx, ny, nrx, nry)) return true;
    }
    return false;
}

int main()
{
    while(cin >> n >> m)
    {
        for(int i = 0; i < n; i++) //由于走到迷宫边界后，再往外走坐标要取模，从0开始更便于处理，比如n=5,x=4，(x+1)%5=0
        {
            for(int j = 0; j < m; j++)
            {
                cin >> a[i][j];
                if(a[i][j] == 'S') 
                {
                    x = i;
                    y = j;
                }
            }
        }
        memset(vis, 0, sizeof(vis));
        memset(rrx, 0, sizeof(rrx));
        memset(rry, 0, sizeof(rry));
        if(dfs(x, y, x, y)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}