pipioj 1027: 逃离迷宫（简单bfs）

http://www.pipioj.online/problem.php?id=1027
  1 #define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  2 #define bug(x) cout<<#x<<" is "<<x<<endl
  3 #include <bits/stdc++.h>
  4 #define iter ::iterator
  5 using namespace  std;
  6 typedef long long ll;
  7 typedef pair<int,ll>P;
  8 #define pb push_back
  9 #define mk make_pair
 10 #define se second
 11 #define fi first
 12 #define rs o*2+1
 13 #define ls o*2
 14 const ll mod=1e9+7;
 15 const int N=1e2+5;
 16 int T,n,m,k;
 17 
 18 int sx,sy,ex,ey;
 19 
 20 struct node{
 21     int x,y,z,w;
 22     bool operator <(const node &t)const{
 23         return w>t.w;
 24     }
 25 };
 26 
 27 int dx[4]={1,-1,0,0};
 28 int dy[4]={0,0,1,-1};
 29 
 30 int vis[N][N][4];
 31 
 32 char s[N][N];
 33 
 34 int check(int x,int y,int z){
 35     if(x<1||x>n||y<1||y>m||s[x][y]=='*'||vis[x][y][z])return 0;
 36     return 1;
 37 }
 38 
 39 int cnt;
 40 
 41 int bfs(int r){
 42 
 43     if(s[sx][sy]=='*'||s[ex][ey]=='*')return 0;
 44     if(sx==ex&&sy==ey)return 1;
 45     for(int i=0;i<=n;i++){
 46         for(int j=0;j<=m;j++)for(int h=0;h<4;h++)vis[i][j][h]=0;
 47     }
 48     priority_queue<node>q;
 49     node start;
 50     start.x=sx;
 51     start.y=sy;
 52     start.z=r;
 53     start.w=0;
 54     q.push(start);
 55     vis[sx][sy][r]=1;
 56 
 57     //bug(q.size());
 58     
 59     while(!q.empty()){
 60         node now=q.top(),next;
 61         q.pop();
 62         for(int i=0;i<4;i++){
 63             next.x=now.x+dx[i];
 64             next.y=now.y+dy[i];
 65             next.z=i;
 66             next.w=now.w;
 67             if(check(next.x,next.y,next.z)){
 68                 //printf("cnt=%d %d %d %d %d
",++cnt,next.x,next.y,next.z,next.w);
 69                 vis[next.x][next.y][i]=1;
 70                 if(i!=now.z)next.w++;
 71                 //if(next.x==ex&&next.y==ey)bug(next.w);
 72                 //bug(next.w);
 73                 if(next.w>k)continue;
 74                 if(next.x==ex&&next.y==ey)return 1;
 75                 q.push(next);
 76             }
 77         }
 78     }
 79     return 0;
 80 }
 81 
 82 int main(){
 83 
 84     //IO;
 85     cin>>T;
 86     while(T--){
 87 
 88         cin>>n>>m;
 89         for(int i=1;i<=n;i++){
 90             scanf("%s",s[i]+1);
 91         }
 92         cin>>k>>sy>>sx>>ey>>ex;
 93         int f=0;
 94         for(int i=0;i<4;i++){
 95             if(bfs(i)){
 96                 f=1,puts("yes");
 97                 break;
 98             }
 99         }
100         if(!f)puts("no");
101         
102 
103     }
104 
105 }
106 /*
107 
108 10
109 5 5
110 ...**
111 *.**.
112 .....
113 .....
114 *....
115 2 1 1 1 3
116 
117 */