小X与机器人 (betago) 题解

输入

输出

样例输入 

样例输出 

【数据范围】

题解

方法一：分类讨论

三种情况：

（1）对面两个点，要分两路比较

（2）相邻直线上的两个点（x横坐标y纵坐标）abs(x1-x2)+abs(y1-y2)

（3）同一条线上abs(x1-x2)或abs(y1-y2)

参考代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int solve(int x,int y){
    if(x-y>=0) return x-y;
    return y-x;
}
signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int x1,y1,x2,y2,a,b;
    scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
    if(abs(x1-x2)==18){
        a=18+y1-1+y2-1;
        b=18+19-y1+19-y2; 
    }
    else if(abs(y1-y2)==18){
        a=18+x1-1+x2-1;
        b=18+19-x1+19-x2; 
    }
    else if(x1==x2) a=solve(y1,y2);
    else if(y1==y2) a=solve(x1,x2);
    else a=solve(x1,x2)+solve(y1,y2);
    if((a>b)&&(b!=0)) printf("%lld\n",b);
    else printf("%lld\n",a);
    return 0;
}

方法二：广度优先搜索（BFS）

参考代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
queue<int>x,y,sum;
int vis[20][20],sx,sy,tx,ty,xx,yy,summ;
signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%lld%lld%lld%lld",&sx,&sy,&tx,&ty);
    if(sx==tx&&sy==ty){
        printf("0\n");
        return 0;
    }
    x.push(sx),y.push(sy),sum.push(0);
    while(!x.empty()){
        xx=x.front(),yy=y.front(),summ=sum.front();
        vis[xx][yy]=summ;
        if(xx==1||xx==19){
            if(yy<19&&vis[xx][yy+1]==0)
                x.push(xx),y.push(yy+1),sum.push(summ+1);
            if(yy>1&&vis[xx][yy-1]==0)
                x.push(xx),y.push(yy-1),sum.push(summ+1);
        }
        if(yy==1||yy==19){
            if(xx<19&&vis[xx+1][yy]==0)
                x.push(xx+1),y.push(yy),sum.push(summ+1);
            if(xx>1&&vis[xx-1][yy]==0)
                x.push(xx-1),y.push(yy),sum.push(summ+1);
        }
        if(xx==sx&&yy==sy) vis[xx][yy]=1;
        x.pop(),y.pop(),sum.pop();
    }
    printf("%lld\n",vis[tx][ty]);
    return 0;
}