AT_abc323_f [ABC323F] Push and Carry

思路

首先我们发现，刚开始人需要走到箱子周围的四个位置。其次我们发现人需要站的位置最多有两个。

例如，$c$ 在 $b$ 左方，人就需要在箱子右方。

然后我们就可以算出 $a$ 点走到这两个点的距离，需要注意的是，这两点所产生的贡献不一定是两点间的曼哈顿距离，因为如果 $b$ 挡在了 $a$ 和该点之间，贡献需要加 $2$。

接着我们选择走最近的点，然后发现如果不考虑后续转向的贡献，距离就是 $b,c$ 间的曼哈顿距离。然后加上转向的贡献即可。

Code

#include <bits/stdc++.h>
#define re register
#define int long long

using namespace std;

typedef pair<int,int> pii;
int ans;
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
bool w[10];
vector<int> v;

struct point{
    int x,y;
}a,b,c;

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline int dist(point a,point b){
    return abs(a.x - b.x) + abs(a.y - b.y);
}

signed main(){
    a.x = read(),a.y = read();
    b.x = read(),b.y = read();
    c.x = read(),c.y = read();
    if (c.y < b.y) w[1] = true;
    else if (c.y > b.y) w[0] = true;
    if (c.x < b.x) w[3] = true;
    else if (c.x > b.x) w[2] = true;
    for (re int i = 0;i < 4;i++){
        if (!w[i]) continue;
        int tx = b.x + dx[i];
        int ty = b.y + dy[i];
        int cnt = dist(a,{tx,ty});
        if ((a.x == b.x && ((a.y < b.y && b.y < ty) || (ty < b.y && b.y < a.y))) || (a.y == b.y && ((a.x < b.x && b.x < tx) || (tx < b.x && b.x < a.x)))) cnt += 2;
        v.push_back(cnt);
    }
    sort(v.begin(),v.end());
    ans = v.front() + dist(b,c);
    if (v.size() == 2) ans += 2;
    printf("%lld",ans);
    return 0;
}