最小转弯问题

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

代码

#include<stdio.h>

#include<iostream>

using namespace std;

const int dx[5]={0,1,-1,0,0};

const int dy[5]={0,0,0,1,-1};

int n,m,a[10005][10005],x1,y1,x2,y2,st[1005][4];

void bfs(){

	int head=0,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];

			int y=st[head][2]+dy[i];

			while(x>=1 and x<=n and y>=1 and y<=m and a[x][y]==0){ //如果没有出界而且能走，就一直走

				if(x==x2 and y==y2){ //判断是不是满足条件

					printf("%d",st[tail][3]);

					return ;

				}

				tail++;

				a[x][y]=1;

				st[tail][1]=x;

				st[tail][2]=y;

				st[tail][3]=st[head][3]+1; //是st[head][3]的转弯数加一

				x+=dx[i];

				y+=dy[i];

			}

		}

	}while(head<tail);

}

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

	 for(int j=1;j<=m;j++)

	  scanf("%d",&a[i][j]);

	scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

	bfs();

	return 0;

}

巴特西

[BFS]最小转弯问题

最小转弯问题

最新文章

热门文章