【题目链接】:http://codeforces.com/problemset/problem/196/B

【题意】



给你一个n*m的棋盘;

然后你能够无限复制这个棋盘;

在这个棋盘上你有一个起点s;

然后问你,你能不能从这个起点s开始一直走无限远;

【题解】



考虑两个不同棋盘上的点(x1,y1),(x2,y2)(即复制出的另外一个棋盘);

假设他们在第一个棋盘上对应的投影x%n,y%m是相同的;

且它们都能由起点S到达;

即S能到达这两个点;

则可知;

可以从S到达其中的一个点(x1,y1);

然后从那个点再到起点,然后再到另外一个棋盘上的(x2,y2),然后再一直重复上述步骤,再回到(x1,y1)再到(x2,y2)..就能无限延伸了;

必要性是靠直觉的吧;

感觉就是要能一直从一个点然后又回到这个点,才能一直扩展嘛;

做法就是dfs(x,y);

看看vis[x%n][y%m]存的是不是(x,y);

不是的话就输出有解;

(vis[x%n][y%m]和(x,y)就是上面对应的(x1,y1)和(x2,y2) )

否则结束这一层递归;



【Number Of WA】



1



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0),cin.tie(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int M = 1500+10;

bool a[M][M],bo[M][M];

pii vis[M][M];

int n,m,x,y;

char s[M];

void out(){

    cout <<"Yes"<<endl;

    exit(0);

}

void dfs(int x,int y){

    int tx = (x%n+n)%n,ty = (y%m+m)%m;

    if (!a[tx][ty]) return;

    if (bo[tx][ty]){

        if (vis[tx][ty].fi !=x || vis[tx][ty].se != y)

            out();

        return;

    }

    else

        bo[tx][ty] = true,vis[tx][ty] = mp(x,y);

    rep1(i,1,4){

        int tx = x+dx[i],ty = y+dy[i];

        dfs(tx,ty);

    }

}

int main(){

    //Open();

    Close();//scanf,puts,printf not use

    //init??????

    cin >> n >> m;

    rep1(i,0,n-1){

        cin >>s;

        rep1(j,0,m-1){

            if (s[j]=='#')

                a[i][j] = 0;

            else{

                a[i][j] = 1;

                if (s[j]=='S'){

                    x = i,y = j;

                }

            }

        }

    }

    dfs(x,y);

    cout <<"No"<<endl;

    return 0;

}