Time Limit: 10 second
Memory Limit: 2 MB
问题描述
给出一张地图，这张地图被分为n*m（n，m<=100）个方块，任何一个方块不是平地就是高山。平地可以通过，高山则不能。现在你处在地图的（x1,y1)这块平地，问：你至少需要拐几个弯才能到达目的地(x2,y2)？你只能沿着水平和垂直方向的平地上行进，拐弯次数就等于行进方向的改变（从水平垂直或从垂直到水平）次数
Input
第1行： n m 第1至n+1行：整个地图地形描述（0:空地；1：高山）， 第2行地形描述为： 1 0 0 0 0 1 0 第3行地形描述为： 0 0 1 0 1 0 0 ......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
【题解】
这题,用广搜来做。
因为广搜。可以按照转弯1次,转弯2次...的顺序进行扩展节点。
因此先前已经走过的点一定不会再入队一次。
可以用一个cost[x][y]数组，来记录从起点到x,y坐标的所需要的最少转弯次数。
一开始cost[x][y]等于正无穷，然后cost[x0][y0] = 0，x0yo是起点坐标。然后从x0,y0开始扩展节点。因为是以转弯次数为花费。所以认定一个方向之后可以一直走到头。
然后我们每次到达一个点，都递增一次转弯次数。这样的结果就是，最后会多算了一次转弯次数。最后减掉就可以了(扩展的话是4个方向定义两个常量数组就可以解决了)
【代码】
#include <cstdio>
#include <cstring>
struct po //用po结构体来记录一个点的坐标
{
int x,y;
};
const int dx[5] = {0,0,0,1,-1}; //表示往4个方向扩展
const int dy[5] = {0,1,-1,0,0};
int n,m,a[101][101],x1,y1,x2,y2,cost[101][101];
po dl[10010];
int main()
{
//freopen("F:\rush.txt","r",stdin);
memset(a,255,sizeof(a));
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); //读入起点和终点的坐标
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++) //一开始置初值为正无穷
cost[i][j] = 2100000000;
cost[x1][y1] = 0; //起点的花费为0，表示不用转弯就能到
dl[1].x = x1;dl[1].y = y1; //把起点坐标加入队列中
int head = 0,tail = 1;
while (head != tail) //进行广搜
{
head ++;
int xx = dl[head].x,yy = dl[head].y; //取出头结点
for (int i = 1;i <= 4;i++) //然后往4个方向扩展
{
int tx = xx,ty = yy;
while (a[tx+dx[i]][ty+dy[i]] == 0) //认准一个方向之后，如果这个方向还能走，就一直走
{
tx+=dx[i],ty+=dy[i];
if (cost[tx][ty] > cost[xx][yy] + 1) //如果txty是第一次到达。则一定可以更新的
{ //如果txty之前已经到达过。则不可能会更新。这样保证每个点都只最多入队一次
cost[tx][ty] = cost[xx][yy] +1;
tail++;
dl[tail].x = tx;
dl[tail].y = ty;
if (tx == x2 && ty == y2) //如果到达了终点，直接输出记录的值减去1，因为开始的时候多算了1次
{
printf("%d
",cost[tx][ty]-1);
return 0;
}
}
}
}
}
return 0;
}