BZOJ1193/HNOI2006/马步距离

Posted on By 二价氢

#题目描述

#做法

暴力啊,瞎搞啊,搜索啊,随便搞搞就过了

#复杂度分析 \(O(n)\)

#AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <utility>
using namespace std;
#define x first
#define y second
const int dx[]={ 1, 1,-1,-1, 2, 2,-2,-2},
          dy[]={ 2,-2, 2,-2, 1,-1, 1,-1},
          delta=20;
int x1,x2,y1,y2,x,y,ans;
int dis[40][40];
bool vis[40][40];
typedef pair<int,int> pii;
void bfs()
{
    pii u;
    queue<pii>Q;
    Q.push(pii(delta,delta));
    memset(vis,0,sizeof(vis));memset(dis,0x3f,sizeof(dis));
    dis[delta][delta]=0;
    while (!Q.empty())
    {
        u=Q.front();Q.pop();vis[u.x][u.y]=false;
        for (int i=0;i<8;i++)
        {
            if (u.x+dx[i]>=0 && u.y+dy[i]>=0 && u.y+dy[i]<40 && u.x+dx[i]<40)
            {
                if (dis[u.x+dx[i]][u.y+dy[i]]>dis[u.x][u.y]+1)
                {
                    dis[u.x+dx[i]][u.y+dy[i]]=dis[u.x][u.y]+1;
                    if (!vis[u.x+dx[i]][u.y+dy[i]])
                    {
                        vis[u.x+dx[i]][u.y+dy[i]]=true;
                        Q.push(pii(u.x+dx[i],u.y+dy[i]));
                    }
                }
            }
        }
    }
}
int main()
{
    bfs();
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    x=abs(x1-x2);y=abs(y1-y2);
    while (x>=18 ||  y>=18)
    {
        if (x>y)
            x-=2,y-=1;
        else
            x-=1,y-=2;
        ans++;
        x=abs(x);y=abs(y);
    }
    ans+=dis[x+delta][y+delta];
    printf("%d\n",ans);
    return 0;
}