本文共 1851 字，大约阅读时间需要 6 分钟。

Description

给出一张地图，这张地图被分为 n×m（n,m<=100）个方块，任何一个方块不是平地就是高山。平地可以通过，高山则不能。现在你处在地图的（x1,y1）这块平地，问：你至少需要拐几个弯才能到达目的地（x2,y2）？你只能沿着水平和垂直方向的平地上行进，拐弯次数就等于行进方向的改变（从水平到垂直或从垂直到水平）的次数。例如：如图 1，最少的拐弯次数为5。

Input

第 1行：n m 第 2至n+1行：整个地图地形描述（0：空地；1：高山）， 如图,第2行地形描述为：1 0 0 0 0 1 0 第3行地形描述为：0 0 1 0 1 0 0 …… 第n+2行：x1 y1 x2 y2 （分别为起点、终点坐标）

Output

s （即最少的拐弯次数

Sample Input

5 71 0 0 0 0 1 00 0 1 0 1 0 0  0 0 0 0 1 0 1  0 1 1 0 0 0 0  0 0 0 0 1 1 0 1 3 1 7

Sample Output

5

分析&说明：

这道题我的主体部分还是广搜模板 。就是输出函数那里改了1点点地方·。以下为输出函数：

void print(int x){   	if (father[x]==0) return;	else print(father[x]);	if(state[x][1]-state[father[x]][1]==0) f=2; else f=1;    if(father[father[x]]==0) b=f;    if(b!=f) s++,b=f;}

s为统计变量,b=s;f为判断当前的走法(平行或垂直)，b为判断上一次的走法，方便看出是否有转弯（垂直就是转弯)。

代码：

#include
   
    #include
    
     using namespace std;int b,f,m,n,a[101][101],state[11000][3],s,father[11000],x,y,px,py,best;short dx[5]={   0,1,0,-1,0},dy[5]={   0,0,1,0,-1};char c;bool check(int x,int y){   	//判断非法函数	if (1>x||x>n||1>y||y>m||a[x][y]==1) return false;	return true;}void print(int x){   	if (father[x]==0) return;	else print(father[x]);	if(state[x][1]-state[father[x]][1]==0) f=2; else f=1;    if(father[father[x]]==0) b=f;    if(b!=f) s++,b=f;    //转弯函数(输出函数)}void bfs(){   	int tail,head;	state[1][1]=x;state[1][2]=y;state[1][3]=0;tail=1;head=0;	do	{   	//广搜主体		head++;		for (int i=1;i<=4;i++)		{   	        if(check(state[head][1]+dx[i],state[head][2]+dy[i]))	        {   			    tail++;			    father[tail]=head;		 	    state[tail][1]=state[head][1]+dx[i];		 	    state[tail][2]=state[head][2]+dy[i];				a[state[tail][1]][state[tail][2]]=1;	  				if (state[tail][1]==px&&state[tail][2]==py)				{   				    print(tail);				    tail=0;				}      		        }		}	}	while (head
     
      >n>>m;	for (int i=1;i<=n;i++)	 for (int j=1;j<=m;j++)	 cin>>a[i][j];	  cin>>x>>y>>px>>py;	bfs();	cout<