http://acm.hdu.edu.cn/showproblem.php?pid=1728
//1302018 2009-04-23 19:16:46 Accepted 1728 31MS 332K 1788 B C++ no way #include<iostream> #include<queue> #include<stdio.h> using namespace std; struct Node { int x; int y; }; int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; char map[102][102]; int m,n,step; int ok,sx,sy,ex,ey; int mark[102][102]; void Init() { int i,j; cin>>m>>n; for(i=0;i<m;i++) for(j=0;j<n;j++) mark[i][j] = -1; for(i=0;i<m;i++) scanf("%s",map[i]); scanf("%d%d%d%d%d",&step,&sy,&sx,&ey,&ex); sx --; sy --; ex --; ey --; }
void bfs() { int k,turns; Node q,p; queue<Node>Q; p.x = sx; p.y = sy; Q.push(p); while(!Q.empty()) { q = Q.front(); Q.pop(); turns = mark[q.x][q.y] + 1; for(k=0;k<4;k++)//四方向,每个方向都走到底 { p.x = q.x+dir[k][0]; p.y = q.y+dir[k][1]; while(p.x>=0 && p.x<m && p.y>=0 && p.y<n && map[p.x][p.y] == '.')// { if(mark[p.x][p.y] == -1) { if(p.x == ex && p.y== ey && turns <= step ) {//最先搜到的就是最优的, ok = 1; return ; } mark[p.x][p.y] = turns; Q.push(p); } p.x += dir[k][0]; p.y += dir[k][1]; } }//for(k=0;k<4;k++) }//while(!Q.empty()) }
int main() { int t; cin>>t; while(t--) { Init(); if(sx==ex&&sy==ey) { printf("yes\n"); continue; } ok = 0; bfs(); if( ok == 1) cout<<"yes"<<endl; else cout<<"no"<<endl; } return 0; }
|