【rest】搜索练习五

描述 Description

考虑一个 N x N (1 <= N <= 100)的有1个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的，它们被标记为了‘x‘。例如下图：

. . B x .
. x x A .
. . . x .
. x . . .
. . x . .

贝茜发现自己恰好在点A处，她想去B处的盐块舔盐。缓慢而且笨拙的动物，比如奶牛，十分讨厌转弯。尽管如此，当然在必要的时候她们还是会转弯的。对于一个给定的牧场，请你计算从A到B最少的转弯次数。开始的时候，贝茜可以使面对任意一个方向。贝茜知道她一定可以到达。

输入格式 InputFormat

第 1行: 一个整数 N 行.

2..N + 1: 行 i+1 有 N 个字符 (‘.‘, ‘x‘, ‘A‘, ‘B‘)，表示每个点的状态。

输出格式 OutputFormat

行 1: 一个整数，最少的转弯次数。

样例输入 SampleInput

8
.Bxx....
........
........
.x.....A
........
........
........
........

样例输出 SampleOutput

#include <stdio.h>

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int inf=0x7fffffff/27.11;

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

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

struct point

{

    int z,y,x;

}q[100000];

char a[105][105];

int f[105][105][5];

bool b[105][105][5];

int i,j,t,n,m,l,r,k,z,y,x,sx,sy,ex,ey;

char ch;

int main()

{

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

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

    {

        for (j=1;j<=n;j++)

        {

            ch=getchar();

            a[i][j]=ch;

            if (a[i][j]==‘A‘) sx=i,sy=j;

            if (a[i][j]==‘B‘) ex=i,ey=j;

        }

        ch=getchar();

    }

    memset(b,false,sizeof(b));

    for (i=1;i<=n;i++) for (j=1;j<=n;j++) for (k=1;k<=4;k++) f[i][j][k]=inf;

    l=1;r=0;

    for (i=1;i<=4;i++)

    {

        q[++r].x=sx;q[r].y=sy;q[r].z=i;

        b[q[r].x][q[r].y][q[r].z]=true;

        f[q[r].x][q[r].y][q[r].z]=0;

    }

    while (l<=r)

    {

        for (i=1;i<=4;i++)

        {

            int tx=q[l].x+dx[i];

            int ty=q[l].y+dy[i];

            int tz=f[q[l].x][q[l].y][q[l].z]+(q[l].z!=i);

            if (tx<=0 || tx>n || ty<=0 || ty>n || a[tx][ty]==‘x‘) continue;

            if (tz<f[tx][ty][i])

            {

                f[tx][ty][i]=tz;

                if (b[tx][ty][i]==false)

                {

                    q[++r].x=tx;q[r].y=ty;q[r].z=i;

                    b[tx][ty][i]=true;

                }

            }

        }

        b[q[l].x][q[l].y][q[l].z]=false;

        l++;

    }

    int ans=inf;

    for (i=1;i<=4;i++) ans=min(ans,f[ex][ey][i]);

    printf("%d\n",ans);

    return 0;

}