Infinite Maze CodeForces - 197D

题意：给定一个可以无限拼接的图，已知起点S，问你是不是能无限走下去。
思路：如何能无限走下去呢? 对于一个田字图，只要在1中可以到达的点，从第一幅图的S在234中依旧可以到达，那么接下来就是重复上次的操作。对于越界的情况，1等效2
对于为什么是4张图的原因是，1图可以延伸234就可以延伸到任意点

/*** Welcome To See My Code ***/
/***If I get TLE , it is good.If I get AC,it's NICE !***/
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <map>
using namespace std;
typedef long long ll;
const int INF=2147483647;
const int MAXN=1e5+10;
const ll mod=1e9+7;
using namespace std;
typedef long long ll;
char mp[3500][3500];
bool vis[3200][3200];
int n,m,sx,sy;
int que[3020*3020];
int dir[4][2]={-1,0,1,0,0,-1,0,1};

bool bfs()
{
    memset(vis,false,sizeof(vis));
    int ft=0,ed=0;
    que[ed++]=sx,que[ed++]=sy;
    vis[sx][sy]=true;
    while(ft<ed)
    {
        int x=que[ft++];
        int y=que[ft++];
        for(int i=0;i<4;i++)
        {
            int nx=x+dir[i][0];
            int ny=y+dir[i][1];
            if(nx<=0)   nx+=2*n;
            else if(nx>=2*n+1)  nx-=2*n;
            if(ny<=0)   ny+=2*m;
            else if(ny>=2*m+1)  ny-=2*m;
            if(nx>=1 && nx<=2*n && ny>=1 && ny<=2*m && vis[nx][ny]==false && mp[nx][ny]=='.')
            {
                vis[nx][ny]=true;
                que[ed++]=nx,que[ed++]=ny;
                int basex=nx,basey=ny;
                int cnt=0;
                if(basex>n) basex-=n;
                if(basey>m) basey-=m;
                if(vis[basex][basey])    cnt++;
                if(vis[basex+n][basey])    cnt++;
                if(vis[basex+n][basey+m])    cnt++;
                if(vis[basex][basey+m])    cnt++;
                if(cnt==2)  return true;
            }
        }
    }
    return false;
}

int main(void)
{
    n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",mp[i]+1);
        for(int j=1;j<=m;j++)
        {
            if(mp[i][j]=='S')
            {
                sx=i,sy=j;
                mp[i][j]='.';
                break;
            }
        }
    }
    //
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            mp[i+n][j]=mp[i][j];
            mp[i+n][j+m]=mp[i][j];
            mp[i][j+m]=mp[i][j];
        }
    }
    /*puts("");puts("");puts(""); // Checking your input and output is an important thing! for(int i=1;i<=2*n;i++) { for(int j=1;j<=2*m;j++) { printf("%c",mp[i][j]); } puts(""); } puts("");puts("");puts(""); */
    /*for(int i=1;i<=2*n;i++) { for(int j=1;j<=2*m;j++) { printf("%d",vis[i][j]); } puts("");*/

    if(bfs())   printf("Yes\n");
    else    printf("No\n");
}


/*debug 12 12 ##.#######.# #..#......S# #.#..####### ..#.###..... ##..##..#### #..##..##### ..##..#..... ###..##.#### ##..#...#### #..##.###### ..##..####.. ##...#####.# */

这道题还是看了学长的代码才知道，问了几遍才明白。刚看这题的时候确实这样想了，后来还是没做放弃了。简单点一个字菜把

通过这题我学到了什么？
1.一个等价的过程，往左走到某个点等价于从右边走到某个点。
2.一定要经常回顾曾经做不出来的题目，这样价值会非常大