2 5 5 ...** *.**. ..... ..... *.... 1 1 1 1 3 5 5 ...** *.**. ..... ..... *.... 2 1 1 1 3
no yes
思路：BFS。注意行列不要弄错。
#include <stdio.h>
#include <string.h>
#define INF 999999999
struct{ //fx[4]代表4个不同方向，搜索的时候如果下一步的转弯次数比当前点到下一点的次数小就把
int count,x,y; //四个方向标志置零，然后fx[i]=1并且更新最小次数
bool fx[4]; //如果相等就直接fx[i]=1;
}pt[101][101],*que[100000];
char map[101][102];
int T,m,n,k,x1,y1,x2,y2,top,bottom,next[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
bool search()
{
int i,j,x,y,count,tempcnt,min=INF;
top=0;
bottom=1;
que[0]=&pt[x1][y1];
for(i=0;i<4;i++) pt[x1][y1].fx[i]=1;
pt[x1][y1].x=x1;
pt[x1][y1].y=y1;
pt[x1][y1].count=0;
while(top<bottom)
{
x=que[top]->x;
y=que[top]->y;
count=que[top]->count;
if(x==x2 && y==y2 && count<=k)
{
if(count<min) min=count;
}
else
{
for(i=0;i<4;i++)//向四个方向拓展
{
if(x+next[i][0]>0 && x+next[i][0]<=m && y+next[i][1]>0 && y+next[i][1]<=n)//不越界
{
if(map[x+next[i][0]][y+next[i][1]]==‘.‘)//无障碍
{
if(!que[top]->fx[i]) tempcnt=count+1;
else tempcnt=count;
if(tempcnt<pt[x+next[i][0]][y+next[i][1]].count && tempcnt<=k)
{
que[bottom++]=&pt[x+next[i][0]][y+next[i][1]];
for(j=0;j<4;j++) pt[x+next[i][0]][y+next[i][1]].fx[j]=0;//更新方向
pt[x+next[i][0]][y+next[i][1]].fx[i]=1;
pt[x+next[i][0]][y+next[i][1]].x=x+next[i][0];//更新坐标
pt[x+next[i][0]][y+next[i][1]].y=y+next[i][1];
pt[x+next[i][0]][y+next[i][1]].count=tempcnt;//更新转弯次数
}
else if(tempcnt==pt[x+next[i][0]][y+next[i][1]].count && tempcnt<=k)
{
pt[x+next[i][0]][y+next[i][1]].fx[i]=1;//更新方向
}
}
}
}
}
top++;
}
if(min<INF) return 1;
else return 0;
}
int main()
{
int i,j;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&m,&n);
for(i=1;i<=m;i++) scanf("%s",&map[i][1]);
scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++) pt[i][j].count=INF;
}
if(search()) printf("yes\n");
else printf("no\n");
}
}
HDU-1728-逃离迷宫(BFS),布布扣,bubuko.com
原文：http://blog.csdn.net/faithdmc/article/details/20123503