URAL/1377

来自"NOCOW"

两遍bfs。。。各种水题。

#include <cstdio>
#include <cstdlib>
#include <cstring>
const int mov[4][2]={1,0,0,1,-1,0,0,-1};
struct node
{
    int x,y;
    node()
    {
        x=y=0;
    }
}u,v,a,b;
bool f[102][102]={false},g[102][102]={false};
int n,m,t1=0,t2=0;
void bfs(bool visit[102][102],const node& t,int& step)
{
    int dire=0;
    u.x=u.y=1;
    while (true)
    {
        visit[u.y][u.x]=true;
        if ((u.x == t.x) && (u.y == t.y))
            return;
        ++step;
        for (int i=dire;(i+1&3)!=dire;i=(i+1&3))
        {
            v.x=mov[i][0]+u.x;
            v.y=mov[i][1]+u.y;
            if (!visit[v.y][v.x])
            {
                u=v;
                dire=i;
                break;
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%d%d",&a.y,&a.x);
    scanf("%d%d",&b.y,&b.x);
    for (int i=0;i<=n+1;++i)
        f[i][0]=f[i][m+1]=true;
    for (int i=0;i<=m+1;++i)
        f[0][i]=f[n+1][i]=true;
    memcpy(g,f,sizeof(f));
    bfs(f,a,t1);
    bfs(g,b,t2);
    if (t1 < t2)
    {
        t1^=t2;
        t2^=t1;
        t1^=t2;
    }
    printf("%d\n",t1-t2);
    return 0;
}
//by zzy