洛谷P1363 幻象迷宫题解

题意：

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

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

输入格式：

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

每组数据的第一行是两个整数 $n,m$ 。

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

输出格式：

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

数据范围：

$n,m \le 1500$，每个测试点不超过 $10$ 组数据。

考虑将所有 $(x \bmod n, y \bmod m)$ 相同的点 $(x,y)$ 看作一个集合

若至少存在一个集合 $S$ ，使得两个点 $(x_1,y_1), ~(x_2,y_2) \in S$ 可以相互到达，则原问题有解（能无限走）

我们可以用搜索来解决这个问题，在搜索的过程中记录实际坐标和 $\bmod$ 后的坐标

如果一个 $\bmod$ 后的点第一次到达，则记录此时的真实坐标。

否则检验是否与第一次的真实坐标相同。如果相同就返回（这个可以直接在搜索前判断。）

时间复杂度 $\mathcal{O}(Tmn)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define SAFE (vis[tx][ty][1] != tlx || vis[tx][ty][2] != tly || vis[tx][ty][0] != tim)
#define N ((int)(1500 + 15))

const int dx[5] = {1,-1,0,0};
const int dy[5] = {0,0,1,-1};
int n,m,vis[N][N][3],tim = 1; bitset<N> mp[N]; char ok, str[N];
void dfs(int x,int y,int lx,int ly)
{
    if(ok) return;
    if(vis[x][y][0] == tim && (vis[x][y][1] != lx || vis[x][y][2] != ly))
        return ok = 1, void(0);
    vis[x][y][0] = tim, vis[x][y][1] = lx, vis[x][y][2] = ly;
    for(int i = 0; i < 4; i++)
    {
        int tx = (x + dx[i] + n) % n, ty = (y + dy[i] + m) % m;
        int tlx = lx + dx[i], tly = ly + dy[i];
        if(!mp[tx][ty] && SAFE) dfs(tx,ty,tlx,tly);
    }
}
void clear()
{
    ok = 0; ++tim; 
    for(int i = 0; i < n; i++) mp[i] = 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    while(cin >> n >> m)
    {
        clear(); int sx = -1,sy = -1;
        for(int i = 0; i < n; i++)
        {
            cin >> str;
            for(int j = 0; j < m; j++)
            {
                if(str[j] == '#') mp[i][j] = 1;
                if(str[j] == 'S') tie(sx, sy) = {i,j};
            }
        }
        dfs(sx,sy,sx,sy); cout << (ok ? "Yes" : "No") << '\n';
    }
    return 0;
}