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;
}
|