[BZOJ1644]&&[Usaco2007 Oct]Obstacle Course 障碍训练课

描述 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

2

来源 Source

Silver


BZOJ 1644


代码 Code

每个点拆成四个方向,bfs.

#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("%dn",&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;
}