AT_abc323_f [ABC323F] Push and Carry 题解

不难发现答案的下界为 \(|x_b-x_c|+|y_b-y_c|\)，这是每步都推箱子的情况。

但很多时候并不能直接开始推箱子，所以人要先移动到箱子的后面（相对于目的地），再把箱子往目的地推。

比如这种情况（B 为箱子，C 为目的地）：

B..
...
..C

推完箱子的一边后，还要走到另一边：

↓
B..   ...  ...
...   ...  ...
..C  →B.C  ..B

额外的代价就是人走到箱子边上（下一步开始推）的时间加上换边的时间 \(2\)（如果有）。

特判掉不用换边的情况后，再计算人到箱子两边的距离的最小值即可。

code：

#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
int ax,ay,bx,by,cx,cy,ans;
int get(int x,int y,int tx,int ty)
{
	int cnt=abs(x-tx)+abs(y-ty);
	if(x==tx&&x==bx&&min(y,ty)<by&&by<max(y,ty))cnt+=2;//路径被箱子阻挡
	else if(y==ty&&y==by&&min(x,tx)<bx&&bx<max(x,tx))cnt+=2;
	return cnt;
}
signed main()
{
	cin>>ax>>ay>>bx>>by>>cx>>cy;
	ans=abs(bx-cx)+abs(by-cy);
	if(bx==cx)printf("%lld",get(ax,ay,bx,by+(cy<by?1:-1))+ans);
	else if(by==cy)printf("%lld",get(ax,ay,bx+(cx<bx?1:-1),by)+ans);
	else printf("%lld",ans+2+min(get(ax,ay,bx,by+(cy<by?1:-1)),get(ax,ay,bx+(cx<bx?1:-1),by)));//要换边
}