最小转弯问题

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 7
1 0 0 0 0 1 0
0 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

分析
这题我们可以用广搜BFS
因为代价必须要一样，所以，我们要一条道直接下去，都等于父节点加1，这样才能AC

while(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]==0)//因为要让代价一样，所以要**while**
			{
   
				if(x==x2&&y==y2)//判断
				{
   
					cout<<st[tail][3];
					return;
			    }
			    tail++;
			    a[x][y]=1;//已经走过
			    st[tail][1]=x;//坐标
			    st[tail][2]=y;
			    st[tail][3]=st[head][3]+1;//最小转弯次数
			    x+=dx[i];//随时更新
			    y+=dy[i]; 
			}

还要标记是否走过，更新并记录好坐标
最后输出目标位置，最小转弯次数

AC代码

#include<iostream>
using namespace std;
int dx[5]={
   0,1,-1,0,0};
int dy[5]={
   0,0,0,1,-1};
int tail,head,st[10005][4],x1,x2,y1,y2,n,m,a[105][105];
void bfs()
{
   
	tail=1;
	st[1][1]=x1;st[1][2]=y1;//初始值
	do
	{
   
		head++;
		for(int i=1;i<=4;i++)
		{
   
			int x=st[head][1]+dx[i],y=st[head][2]+dy[i];//移动后的坐标
			while(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]==0)//因为要让代价一样，所以要**while**
			{
   
				if(x==x2&&y==y2)//判断
				{
   
					cout<<st[tail][3];
					return;
			    }
			    tail++;
			    a[x][y]=1;//已经走过
			    st[tail][1]=x;//坐标
			    st[tail][2]=y;
			    st[tail][3]=st[head][3]+1;//最小转弯次数
			    x+=dx[i];//随时更新
			    y+=dy[i]; 
			}
		}
	}while(head<tail); 
}
int main()
{
   
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=m;j++)
	  cin>>a[i][j];
	cin>>x1>>y1>>x2>>y2;//起点和终点
	bfs();  
}

谢谢观看