图论之理想迷宫

标题描述：
幻象迷宫可以以为是无穷大的，不外它由多少个 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复制

2. 5 4
3. ##.#
4. ##S#
5. #..#
6. #.##
7. #..#
8. 5 4
9. ##.#
10. ##S#
11. #..#
12. ..#.
13. #.##

复制代码

输出 #1复制

2. Yes
3. No
6. <strong>思路：</strong>

复制代码

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

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

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

复制代码

边界一：

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

复制代码

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

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

复制代码

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

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

复制代码

碰到以上条件，那么我们就可以克制了。那么我们必要一个标志变量，体现我们找到了答案，然后以这个标志变量为边界退出其他搜索（第一次搜到能走出去就行了）。
 

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

代码：

2. #include<iostream>
3. #include<cstdio>
4. #include<algorithm>
5. #include<cstring>
6. using namespace std;
8. const int MAXN=1600;
9. const int dx[4]={1,-1,0,0};
10. const int dy[4]={0,0,1,-1};
11. //这里是为了方便表示四个方向，学过坐标轴的应该都懂。
12. char a[MAXN][MAXN];
13. bool map1[MAXN<<1][MAXN<<1],map2[MAXN][MAXN];
14. //map1表示有无走到过这个点，map2表示有无走到过映射点
15. //扩展2倍的原因只是为了方便穿越以及映射
16. int n,m,dn,dm;
17. //dn,dm是扩展后的迷宫长宽。
19. //本文的迷宫都是从0开始。
21. bool dfs(int x,int y)//bool表示是否符合要求
22. {
23.         if(x==-1)
24.          return dfs(dn-1,y);
25.         if(x==dn)
26.          return dfs(0,y);
27.         if(y==-1)
28.          return dfs(x,dm-1);
29.         if(y==dm)
30.          return dfs(x,0);
31.     //上面四个就是遇到边界时“穿越”。
32.         const int xx=x%n;
33.         const int yy=y%m;
34.     //方便表示扩展后的迷宫与实际迷宫的对应坐标。
35.         if(map1[x][y] || a[xx][yy]=='#')
36.          return false;//映射是墙或者在扩展迷宫里走过就不符要求
37.         if(map2[xx][yy])
38.          return true;//一一对应了，就返回true
39.         map1[x][y]=true;
40.         map2[xx][yy]=true;
41.     //记得标记
42.         for(int i=0;i<4;i++)
43.          if(dfs(x+dx[i],y+dy[i]))
44.           return true;//遍历四个方向
45.         return false;//防止到了结尾还没有return的保险措施
46. }
48. void input(void)
49. {
50.         while(cin>>n>>m)
51.         {
52.                 dn=n<<1;
53.                 dm=m<<1;
54.                 int beginx,beginy;
55.                 for(int i=0;i<n;i++)//迷宫从0开始哦
56.                  for(int j=0;j<m;j++)
57.                  {
58.                          cin>>a[i][j];
59.                          if(a[i][j]=='S')
60.                          {
61.                                  beginx=i;
62.                                  beginy=j;
63.                          }//别忘了记录起始点
64.                  }
65.                 memset(map1,0,sizeof(map1));
66.                 memset(map2,0,sizeof(map2));
67.         //别忘了每次清零映射数组
68.                 cout<<((dfs(beginx,beginy))?"Yes":"No")<<endl;
69.         }
70. }
72. int main()
73. {
74.         input();
75.         return 0;
76. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。