题目描述

当WJ醒来时，发现自己被困在一个地图的左上角，幸好WJ有张图，并了解到出口正是迷宫的右下角，至少有一条路径可以到达出口。
整个地图有些地方会有障碍（保证左上角右下角没有），WJ可以快速奔跑，只是需要拐弯时令人很不爽。为了保持心情愉悦，WJ想知道最少需要几次转弯。

输入

第一行两个数r，c表示地图大小
接下来r行，每行c个字符，‘*’代表此处有障碍，‘0’代表空地。

输出

一个数，表示最少需要几次转弯。数据保证有解。

思路

这题的基础是广度优先搜索，但和普通的略有不同
每一个节点我们都让他向四周扩展，扩展的节点的转弯数为头节点+1（起始为-1），一直扩展到遇到障碍或当前节点已被扩展为止

#include 
#include 
using namespace std;
int state[500000],t[500000][3],a[1000][1000],f[500000],l[500000][3];
int dx[5]={1,0,-1,0};
int dy[5]={0,-1,0,1};
int n,m,s,j,k,y,ans=100000,x=0;
char ch[1000];
int bfs()
{
    int head=0,tail=1;
    t[1][1]=1; t[1][2]=1;
    state[1]=-1;
    while (head    {
        head=head+1;
        for (int i=1;i<=4;i++)
        {
            j=dx[i-1];k=dy[i-1];x=t[head][1];y=t[head][2];
            while (a[x+j][y+k]==0&&x+j>0&&x+j0&&y+k            {
                tail=tail+1;
                t[tail][1]=x+j;
                t[tail][2]=y+k;
                state[tail]=state[head]+1;
                x=x+j;
                y=y+k;
                a[x][y]=1;
                if (x==n&&y==m)
                {
                    printf("%d\n",state[tail]);
                    return 0;
                }
            }   
        }
    }
    return 0;
}
int main()
{
    freopen("escape.in", "r", stdin);
   freopen("escape.out", "w", stdout);
    scanf("%d%d\n",&n,&m);
    a[1][1]=1;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            scanf("%c",&ch);
            if (ch[0]=='\n') scanf("%c",&ch);
            if (ch[0]=='*') a[i][j]=1;
        }

    }   

    bfs();
    return 0;
}