当前位置：首页 > news >正文

图论之幻想迷宫

news 来源：原创 2025/7/18 20:44:28

题目描述：

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

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

输入格式

输入包含多组数据。

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

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

输出格式

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

输入输出样例

输入 #1复制

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

输出 #1复制

Yes
No思路：

走到的点标记下，一开始输入的墙标记为1，走过的地方标记为2；每次走的时候都对长宽的两倍取余，保证不越界，这一点和别人写的思想应该是差不多的。
以上，那么越界的时候我们就传送回去；但是，在这传送之前，我们就可以判断这个地方是否被走过了（上述的越界是超过n*m），如果走过，就意味着我们可以从原来的矩阵走到下一矩阵的该位置，因为地图是无限大的，那么我们是不是就可以认为可以走的出去呢？这么想就是正确的。

对于以上第二点，我们可以把边界写出来。

                  if(x>=n || y>=m)

边界一：

                  f[x%n][y%m]==2

由于我们的填充方式，我们不会重复走我们走过的，这意味着虽然我们越界会被“传送”回来，但是这个位置被填充过了就不能走，那么如果我们回来了，这是不是意味着我们可以无限走呢？那么我们就“离开”了迷宫。

边界二：

                  f[x%n+n][y%m]==2

这个与边界一很像，如果我们到了其他矩阵的相应位置，那么貌似也是可以无限走的，所以其他边界也就很容易得出：

                  f[x%n][y%m+m]==2f[x%n+n][y%m+m]==2

遇到以上条件，那么我们就可以停止了。那么我们需要一个标志变量，表示我们找到了答案，然后以这个标志变量为边界退出其他搜索（第一次搜到能走出去就行了）。

这三张图表示的都是我们可以走到其他矩阵的相应位置，当然，不一定是S走到下一个S。虽然对于二三图在该样例中是不能实现的，但是遇到其他地图就可能了

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;const int MAXN=1600;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
//这里是为了方便表示四个方向，学过坐标轴的应该都懂。
char a[MAXN][MAXN];
bool map1[MAXN<<1][MAXN<<1],map2[MAXN][MAXN];
//map1表示有无走到过这个点，map2表示有无走到过映射点
//扩展2倍的原因只是为了方便穿越以及映射
int n,m,dn,dm;
//dn,dm是扩展后的迷宫长宽。//本文的迷宫都是从0开始。bool dfs(int x,int y)//bool表示是否符合要求
{if(x==-1)return dfs(dn-1,y);if(x==dn)return dfs(0,y);if(y==-1)return dfs(x,dm-1);if(y==dm)return dfs(x,0);//上面四个就是遇到边界时“穿越”。const int xx=x%n;const int yy=y%m;//方便表示扩展后的迷宫与实际迷宫的对应坐标。if(map1[x][y] || a[xx][yy]=='#')return false;//映射是墙或者在扩展迷宫里走过就不符要求if(map2[xx][yy])return true;//一一对应了，就返回truemap1[x][y]=true;map2[xx][yy]=true;//记得标记for(int i=0;i<4;i++)if(dfs(x+dx[i],y+dy[i]))return true;//遍历四个方向return false;//防止到了结尾还没有return的保险措施} void input(void)
{while(cin>>n>>m){dn=n<<1;dm=m<<1;int beginx,beginy;for(int i=0;i<n;i++)//迷宫从0开始哦for(int j=0;j<m;j++){cin>>a[i][j];if(a[i][j]=='S'){beginx=i;beginy=j;}//别忘了记录起始点}memset(map1,0,sizeof(map1));memset(map2,0,sizeof(map2));//别忘了每次清零映射数组cout<<((dfs(beginx,beginy))?"Yes":"No")<<endl;}
}int main()
{input();return 0;
}

输入格式

输出格式

输入输出样例

相关文章：