2018秦皇岛day3A 马步距离
提交链接：链接地址


#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#include<queue>
#define mod 1000000007
#define inf 2000000000
#define ll long long
using namespace std;
int x,y,ans;
int xp,yp,xs,ys;
int dx[8]={1,1,-1,-1,2,2,-2,-2},dy[8]={2,-2,2,-2,1,-1,1,-1};
int dis[105][105];
int qx[10005],qy[10005];

int dist[50][50]={0};
int bfs(int x,int y)
{
    queue<pair<int,int> >o;
    dist[x][y] = 0;
    o.push(make_pair(x,y));
    while(!o.empty())
    {
       pair<int,int>p;
       p = o.front();
       o.pop();
       x = p.first;
       y = p.second;
       if(x==10&&y==10)
        return dist[x][y];
       for(int i=0;i<8;i++)
       {

        int tx = dx[i]+p.first;
        int ty = dy[i]+p.second;
        if(tx<0||tx>20||ty<0||ty>20)continue;
        dist[tx][ty] = dist[x][y]+1;
        o.push(make_pair(tx,ty));

       }
    }
}
int main()
{

    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    int x,y;
    x = abs(x1-x2);
    y = abs(y1-y2);
    while(x>=10||y>=10)
    {
        if(x>y) x-=2,y--;
        else x--,y-=2;
        ans++;
        x = abs(x);
        y = abs(y);
    }


    x+=10;
    y+=10;
    int u = bfs(x,y);
    printf("%d\n",ans+u);
    return 0;
}