2 5 5 ...** *.**. ..... ..... *.... 1 1 1 1 3 5 5 ...** *.**. ..... ..... *.... 2 1 1 1 3
no yes
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define N 109
#define INF 0x3f3f3f
using namespace std;
char s[N][N];
int t,n,m;
int sx,sy;
int ex,ey;
int k;
int wan[N][N];
struct Node
{
int x,y;
}f,g;
int dis[4][2]={0,1,0,-1,1,0,-1,0};
void bfs()
{
queue<Node>q;
f.x=sx;
f.y=sy;
q.push(f);
memset(wan,INF,sizeof wan);
wan[f.x][f.y]=-1;
while(!q.empty())
{
g=q.front();
q.pop();
if(g.x==ex && g.y==ey && wan[g.x][g.y]<=k)
{
puts("yes");
return;
}
for(int i=0;i<4;i++)
{
f.x=g.x+dis[i][0];
f.y=g.y+dis[i][1];
while(!(f.x<0||f.x>=m ||f.y<0||f.y>=n))
{
if(s[f.x][f.y]=='*')
break;
if(wan[f.x][f.y]<wan[g.x][g.y]+1)
break;
wan[f.x][f.y]=wan[g.x][g.y]+1;
if(wan[f.x][f.y]>k)
break;
if(wan[f.x][f.y]==k && f.x!=ex && f.y!=ey)
break;
q.push(f);
f.x+=dis[i][0];
f.y+=dis[i][1];
}
}
}
puts("no");
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&m,&n);
for(int i=0;i<m;i++)
scanf("%s",s[i]);
scanf("%d %d %d %d %d",&k,&sy,&sx,&ey,&ex);
sy--;
ey--;
sx--;
ex--;
if(sx==ex && sy==ey)
{
cout<<"yes"<<endl;
continue;
}
bfs();
}
return 0;
}
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define N 109
#define INF 0x3f3f3f
using namespace std;
char s[N][N];
int t,n,m;
int sx,sy;
int ex,ey;
int k;
int wan[N][N];
struct Node
{
int x,y;
}f,g;
int dis[4][2]={0,1,0,-1,1,0,-1,0};
int flag;
//void bfs()
//{
// queue<Node>q;
//
// f.x=sx;
// f.y=sy;
// q.push(f);
// memset(wan,INF,sizeof wan);
// wan[f.x][f.y]=-1;
//
// while(!q.empty())
// {
// g=q.front();
// q.pop();
//
// if(g.x==ex && g.y==ey && wan[g.x][g.y]<=k)
// {
// puts("yes");
// return;
// }
//
// for(int i=0;i<4;i++)
// {
// f.x=g.x+dis[i][0];
// f.y=g.y+dis[i][1];
//
// while(!(f.x<0||f.x>=m ||f.y<0||f.y>=n))
// {
// if(s[f.x][f.y]=='*')
// break;
// if(wan[f.x][f.y]<wan[g.x][g.y]+1)
// break;
// wan[f.x][f.y]=wan[g.x][g.y]+1;
//
// if(wan[f.x][f.y]>k)
// break;
// if(wan[f.x][f.y]==k && f.x!=ex && f.y!=ey)
// break;
//
// q.push(f);
//
// f.x+=dis[i][0];
// f.y+=dis[i][1];
//
// }
//
//
// }
//
// }
// puts("no");
//
//}
void dfs(int x,int y,int dir)
{
if(x==ex && y==ey && wan[x][y]<=k)
{
flag=1;
return;
}
if(wan[x][y]>k)
return;
for(int i=0;i<4;i++)
{
int xx=x+dis[i][0];
int yy=y+dis[i][1];
if(xx<0 || xx>=m || yy<0 || yy>=n || s[xx][yy]=='*' ||wan[xx][yy]<wan[x][y])
continue;
if(wan[xx][yy]<wan[x][y]+1 && dir!=-1 && dir!=i)
continue;
wan[xx][yy]=wan[x][y];
if(i!=dir)
wan[xx][yy]++;
dfs(xx,yy,i);
if(flag)
return;
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&m,&n);
for(int i=0;i<m;i++)
scanf("%s",s[i]);
scanf("%d %d %d %d %d",&k,&sy,&sx,&ey,&ex);
sy--;
ey--;
sx--;
ex--;
if(sx==ex && sy==ey)
{
cout<<"yes"<<endl;
continue;
}
flag=0;
memset(wan,INF,sizeof wan);
wan[sx][sy]=-1;
dfs(sx,sy,-1);
if(flag)
puts("yes");
else
puts("no");
//bfs();
}
return 0;
}
原文：http://blog.csdn.net/wust_zjx/article/details/46013467