10.19T1 搜索

实质上就是一个bfs，但是要注意时限
code：
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<queue>
  4 #include<cstdlib>
  5 #include<cstring>
  6 using namespace std;
  7 namespace FastIO
  8 {
  9     const double L=1<<15;
 10     char buffer[L],*S,*T;
 11     inline char gc(){
 12         if(S==T){T=(S=buffer)+fread(buffer,1,L,stdin);
 13         if(S==T)return EOF;}return *S++;
 14     }
 15     inline double Get(){
 16         register char c;register double x=0,f=1;
 17         for(c=gc();c<'0'||c>'9';c=gc()) if(c=='-')f=-1;
 18         while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c-'0'),c=gc();
 19         return x*f;
 20     }
 21 }
 22 using FastIO::Get;
 23 using FastIO::gc;
 24 struct node {
 25     double x,y;
 26 };
 27 node start;
 28 double dx[4]= {0,0,1,-1};
 29 double dy[4]= {1,-1,0,0};
 30 double vis[6500][6500]={0};
 31 char g[6000][6000];
 32 double n,m;
 33 double bfs() {
 34     queue<node>q;
 35     q.push(start);
 36 //    vis[start.x][start.y]=1;
 37     while(!q.empty()) {
 38         node u=q.front();
 39         q.pop();
 40         double x=u.x,y=u.y;
 41         if(vis[x][y])continue;
 42         vis[x][y]=1;
 43         if(x==1||x==3*n||y==1||y==3*m) {
 44             puts("Yes");
 45             return 1;
 46         }
 47         for(double i=0; i<4; i++) {
 48             double tx=x+dx[i],ty=y+dy[i];
 49             if(tx>3*n||tx<1||ty>3*m||ty<1){
 50                 puts("Yes");
 51                 return 1;
 52             }
 53             if(g[tx][ty]=='#')continue;
 54             for(double i=0;i<=2;i++){
 55                 for(double j=0;j<=2;j++){
 56                     if(i==0&&j==0)continue;
 57                 //    cout<<tx+i*n<<" "<<ty+j*m<<'
';
 58                     if(vis[tx+i*n][ty+j*m]){
 59                         puts("Yes");
 60                         return 1;
 61                     }
 62                 }
 63             } 
 64             if(vis[tx][ty]==1)continue;
 65             else {
 66                 q.push((node) {
 67                     tx,ty
 68                 });
 69             }
 70         }
 71     }
 72     return 0;
 73 }
 74 double read() {
 75     double x=0,f=1;
 76     char c=getchar();
 77     while(!isdigit(c)) {
 78         if(c=='-')f=-1;
 79         c=getchar();
 80     }
 81     while(isdigit(c)) {
 82         x=(x<<1)+(x<<3)+c-'0';
 83         c=getchar();
 84     }
 85     return x*f;
 86 }
 87 double main() {
 88 //    freopen("gun.in","r",stdin);
 89 //    freopen("gun.out","w",stdout);
 90     double T;
 91     T=Get();
 92     while(T--) {
 93         memset(vis,0,sizeof vis);
 94         n=Get(),m=Get();
 95         for(double i=1; i<=n; i++) {
 96             for(double j=1; j<=m; j++) {
 97                 char c=gc();
 98                 while(c!='S'&&c!='#'&&c!='.')c=gc();
 99                 g[i][j]=c;
100                 if(g[i][j]=='S') {
101                     start.x=i+n;
102                     start.y=j+m;
103                 }
104                 g[i+n][j]=g[i][j+m]=g[i+2*n][j]=g[i][j+2*m]=g[i+n][j+m]=g[i+n][j+2*m]=g[i+2*n][j+m]=g[i+2*n][j+2*m]=g[i][j];
105             }
106         }
107         if(bfs());
108         else puts("No");
109     }
110     return 0;
111 }
over