题目描述

We’ve got a rectangular n × m-cell maze. Each cell is either passable, or is a wall (impassable). A little boy found the maze and cyclically tiled a plane with it so that the plane became an infinite maze. Now on this plane cell (x, y) is a wall if and only if cell  is a wall.

In this problem  is a remainder of dividing number a by number b.

The little boy stood at some cell on the plane and he wondered whether he can walk infinitely far away from his starting position. From cell (x, y) he can go to one of the following cells: (x, y - 1)(x, y + 1)(x - 1, y) and (x + 1, y), provided that the cell he goes to is not a wall.

Input

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 1500) — the height and the width of the maze that the boy used to cyclically tile the plane.

Each of the next n lines contains m characters — the description of the labyrinth. Each character is either a “#“, that marks a wall, a “.“, that marks a passable cell, or an “S“, that marks the little boy’s starting point.

The starting point is a passable cell. It is guaranteed that character “S” occurs exactly once in the input.

Output

Print “Yes” (without the quotes), if the little boy can walk infinitely far from the starting point. Otherwise, print “No” (without the quotes).

什么玩意……还是看看翻译

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

请你告诉他能否走出幻象迷宫,如果他能走到距离起点无限远处,就认为能走出去。

也是好久之前做的题了,一开始被题意卡了好久,果然语文不好毁一生啊……

大概就是说给出一个01迷宫类的地图,按照这个地图来扩展新地图,类似这样

然后问你是不是可以走无限远。

那么,我们可以很清晰的意识到,如果可以从点(x,y)出发,达到比如(-x,y)或者(x,-y) , (-x,-y) , (x+m,y+n) [假设宽m高n]  , 就可以从这个点再次达到相同的点(即可以从(x,y)出发,达到(i,j)且|i|%n=x , |j|%m=y。),一直这么走下去。

那就搜好了。开一个三维vis数组第一维记录有无被访问,第二维记录被访问时横坐标,第三维纵坐标。

判断重复到达且横纵坐标不同即可。应该注意先判什么后判什么。如果是同一个分矩阵走过去的话自然tx==vis[x][y][0]此处x为|tx|%n,y为|ty|%m,即映射到中心矩阵的位置),就会被判掉。

而且注意tx!=vis[x][y][0]ty!=vis[x][y][1]满足一个即可。

没啥好说的了。。。数据很大注意搜索优化。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

bool mapx[1510][1510]={false};
int vis[1510][1510][3]={0};
int m,n,sx,sy,wayx[4]={0,-1,0,1},wayy[4]={-1,0,1,0},ans=0;

void dfs(int x,int y,int posx,int posy)
{
    if (vis[posx][posy][2] && (vis[posx][posy][0]!=x || vis[posx][posy][1]!=y))
    {
        ans=1;
        return;
    }
    
    if (vis[posx][posy][2] && vis[posx][posy][0]==x && vis[posx][posy][1]==y) return;
    vis[posx][posy][0]=x; vis[posx][posy][1]=y; vis[posx][posy][2]=1;
    register int tox,toy;

    for (int w=0;w<=3;w++)
    {
        tox=(posx+wayx[w]+n)%n; toy=(posy+wayy[w]+m)%m;    
        if (mapx[tox][toy])dfs(x+wayx[w],y+wayy[w],tox,toy);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    register char ch;
    while (cin>>n>>m)
    {
        memset(mapx,false,sizeof(mapx));
        memset(vis,false,sizeof(vis));
        ans=0;
        
        for (int i=0;i<n;i++)
        {    
            for (int j=0;j<m;j++)
            {
                cin>>ch;
                if (ch=='.') mapx[i][j]=true;
                else if (ch=='S')
                {
                    sx=i; sy=j;
                    mapx[i][j]=true; 
                }
            }
        }
        dfs(sx,sy,sx,sy);
        if (ans) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.