欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【洛谷 P1363】幻想迷宫(搜索)

程序员文章站 2022-07-13 11:19:50
...

这题其实可以很简单。

题目叫做“幻想迷宫”,那么我们就幻想一个迷宫。

借用一下@FancyDreams的图片

【洛谷 P1363】幻想迷宫(搜索)

只有左上角第一个\(5*4\)的迷宫是真的,
其他都是我们幻想出来的。

并且,我们幻想自己在中间那个\(5*4\)的迷宫里的S处,我们并不需要开多很多倍的数组,要获取这个位置是'.'还是'#',只需对当前坐标取余\(n,m\)即可。注意一个细节,直接取余的话若\(x=n\),那么取余后就变成0了,所以我们要这样:

\[(x-1)\ mod\ n + 1\]
y坐标同理。每走到一个点标记vis[取模后的坐标] = 当前迷宫的坐标,比如上图中,左上角的迷宫坐标是1,中上那个是2,最中间的是5,右下角的是9。

然后向4个方向拓展,如果这里不是'#',再判断,如果这个位置走过了并且不是在当前幻想的迷宫走的,那么恭喜,\(flag = 1; return;\)。否则继续搜。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define rep(i,m,n) for(int i=m;i<=n;++i)
#define dop(i,m,n) for(int i=m;i>=n;--i)
using namespace std;
inline int read(){
    int s = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')w = -1;if(ch==-1) exit(0); ch = getchar();} //快读小细节,getchar()==-1时直接exit(0);
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0',ch = getchar();
    return s * w;
}
const int MAXN = 1600;
char a[MAXN][MAXN];
int n, m, sx, sy;
int vis[MAXN][MAXN], flag;
int l[] = { 233, -1, 1, 0, 0 }, r[] = { 666, 0, 0, -1, 1 };
inline char get(int x, int y){//获取当前的位置能不能走
    return a[(x - 1) % n + 1][(y - 1) % m + 1];
}
void dfs(int x, int y){
    if(flag) return; //找到了,直接返回
    vis[(x - 1) % n + 1][(y - 1) % m + 1] = ((x / n - !(x % n)) * 3 + (y / m - !(y % m)) + 1); //标记这个位置是在当前幻想的迷宫走的
    rep(i, 1, 4){ //向四个方向拓展
       int X = x + l[i], Y = y + r[i];//X,Y为要到的位置
       if(vis[(X - 1) % n + 1][(Y - 1) % m + 1] && vis[(X - 1) % n + 1][(Y - 1) % m + 1] != ((X / n - !(X % n)) * 3 + (Y / m - !(Y % m)) + 1)){ //如果走过了并且不是在当前迷宫走的,说明可以重复到达这个位置,也就是可以无限的走
         flag = 1;
         return ;
       }
       if(get(X, Y) != '#' && !vis[(X - 1) % n + 1][(Y - 1) % m + 1]) dfs(X, Y); //如果能走,dfs
    }
}
int main(){
    while(233){
      n = read(); m = read();
      rep(i, 1, n) rep(j, 1, m){
         a[i][j] = getchar();
         while(a[i][j] != '.' && a[i][j] != '#' && a[i][j] != 'S')
           a[i][j] = getchar();
         if(a[i][j] == 'S') sx = i, sy = j;
      }
      dfs(sx + n * 100, sy + m * 100);
      memset(vis, 0, sizeof(vis));
      if(flag){
        printf("Yes\n");
        flag = 0;
      }
      else printf("No\n");
    }
    return 0;
}