最少几个转弯

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

输入
第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 （分别为起点、终点坐标）

输出
输出s （即最少的拐弯次数）

样例输入 Copy
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
样例输出 Copy
5

#include<stdio.h>
#include<queue>
using namespace std;
struct note
{
    int x,y,xx,yy,step;     //x,y记录当前的坐标，xx,yy记录前一个的坐标，step记录转弯的次数 
};
queue<note> q;
int p[110][110],n,m,x1,x2,y1,y2;
int dir[4][2]={1,0,0,1,-1,0,0,-1};         //向四个方向变化 
void bfs()
{
    note ans,temp;
    while(!q.empty())
    {
          temp=q.front();
          if(temp.x==x2 && temp.y==y2) { printf("%d\n",temp.step);   break;}
        q.pop();
        note newx;
        for(int i=0;i<4;i++)
        {
            newx.x=temp.x+dir[i][0];
            newx.y=temp.y+dir[i][1];
            if((newx.x>=1 && newx.x<=n  && newx.y>=1 && newx.y<=m && !p[newx.x][newx.y]) )  //判断下一个点是否在方格内以及是否到过 
            {
                if(newx.x!=temp.xx && newx.y!=temp.yy) newx.step=temp.step+1;   //判断 下一个点 和 上上个点 的横坐标和纵坐标 是否都不相等 
                else  newx.step=temp.step;
                newx.xx=temp.x, newx.yy=temp.y;    //保存上一个点 
                q.push(newx);
            }
        }
    }
}


int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int i,j;
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%d",&p[i][j]);
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        if(x1 == x2 && y1 == y2){
            printf("0\n"); 
            break;
        }
         while(!q.empty()){
             q.pop();
        } 
        note ans,temp;
        temp.x=x1, temp.y=y1, temp.xx=x1, temp.yy=y1, temp.step=0;
        q.push(temp);
        bfs();
    }
    return 0;
}