概要

荷物の初期位置 \((X_B,Y_B)\) と目標位置 \((X_C,Y_C)\) が異なることから、高橋君はまず荷物を動かすことができる位置まで移動し、その後荷物を目標位置まで運ぶ必要があります。これより、 高橋君の初期位置と荷物の初期位置のマンハッタン距離を \(d_1=\lvert X_1-X_2\rvert+\lvert Y_1-Y_2\rvert\) 、 荷物の初期位置と荷物の目標位置のマンハッタン距離を \(d_2=\lvert X_2-X_3\rvert+\lvert Y_2-Y_3\rvert\) とすると、高橋君は最低でも \((d_1-1)+d_2=d_1+d_2-1\) 回は行動する必要があります。
これに加えて、高橋君の初期位置と荷物の初期位置の関係および 荷物の初期位置と荷物の目標位置の関係によって最大 \(4\) 回多く行動する必要があります。

これを場合分けによって実装します。 \(X,Y\) 座標それぞれについて大小関係は、どちらが大きいかまたは等しいかで \(3\) 通り \((X_i<X_j,X_i=X_j, X_i>X_j)\) あり、点の位置関係には完全に一致するパターンを除いて \(3\times 3-1=8\) 通り考えられます。さらに \(2\) 組の位置関係を考える必要があることから愚直には \(64\) 通りのパターンを考えなくてはなりません。 各パターンを正しく列挙し、判定条件およびそれぞれの場合において \(d_1+d_2-1\) 回から何回多く行動する必要があるか正しく実装することができればACを獲得することができます。
実際には、対称性を用いれば \(16\) パターンや \(10\) パターン等に減少させることができるため、実装量を考慮するとそのような工夫を用いた方が時間短縮や実装ミスの回避につながるでしょう。
この方針で実装した場合、多くの場合で計算量は \(O(1)\) であり、多少複雑になったとしても実行時間は問題になりません。 よってこの問題を解くことができました。

以下の詳細で行われている工夫は実装上というより証明上の工夫であるため、必ずしもこのような事を考える必要はありません。

詳細

高橋君の初期位置、荷物の初期位置、荷物の目標位置をすべて同じだけ平行移動させても答えは変わらないため、荷物の初期位置が原点 \((0,0)\) にあるとしても問題ありません。さらに、荷物を動かす代わりに高橋君自身も動かず目標地点を動かすと考える事で、問題設定は次のようなものと考えることができます。

高橋君は\(1\) 回の行動で次のことができます。

• 現在 \((X,Y)\) にいるとき、\((X+1,Y),(X-1,Y),(X,Y+1),(X,Y-1)\) のいずれかに動くことができる。ただし、原点に移動することはできない。
• \((1,0)\) にいるとき、荷物の目標地点 \(X\) 座標を \(1\) 増加させることができる。
• \((-1,0)\) にいるとき、荷物の目標地点 \(X\) 座標を \(1\) 減少させることができる。
• \((0,1)\) にいるとき、荷物の目標地点 \(Y\) 座標を \(1\) 増加させることができる。
• \((0,-1)\) にいるとき、荷物の目標地点 \(Y\) 座標を \(1\) 減少させることができる。

荷物の目標地点を原点まで移動させるために高橋君は最小で何回行動必要があるか求めてください。

この問題を解くことを考えます。
荷物の初期地点と荷物の目標地点の間の各座標の大小関係によって、高橋君には必ず訪れなくてはならない座標が存在します。 例えば元の問題の入力において \(X_2<X_3\) であれば、荷物が原点にあるとき、目標地点の \(X\) 座標は正であり、これを原点に移動させるためには \((-1,0)\) を訪れる必要があります。 \(X_2\neq Y_2\) かつ \(X_3\neq Y_3\) の場合は \((\pm 1,0)\) および \((0,\pm 1)\) のうちそれぞれ一方で合計 \(2\) つの地点、それ以外の場合は \((\pm 1,0)\), \((0,\pm 1)\) のうち \(1\) つの地点となります。

高橋君は最低でも (高橋君の初期位置から始めて、訪れる必要のある地点を全て(原点を通ることなく)訪れるために必要な移動回数)\(+\)(目標地点を原点まで移動させるのに必要な最小の行動回数)だけ行動する必要がありますが、逆にこの回数行動するとき、適切なタイミングで目標地点を移動させることで目標を達成することができます。よって、この値が答えとなります。目標地点を原点まで移動させるのに必要な回数は \(\lvert X_2-X_3\rvert+\lvert Y_2-Y_3\rvert\) 回であるため、あとは高橋君の初期位置 \((X_1-X_2,Y_1-Y_2)\) から始めて訪れる必要のある地点を(原点を通ることなく)全て訪れるために必要な移動回数を求めれば良いです。

i) 訪れる必要のある地点が \(1\) つの場合

多くの場合において、\((X_1-X_2,Y_1-Y_2)\) から訪れる必要のある地点\((X',Y')\) \(\bigl(\)\((X',Y')\) は \((\pm 1,0)\), \((0,\pm 1)\) のいずれか \(\bigr)\) まで原点を通らずに \(\lvert (X_1-X_2)-X'\rvert+\lvert (Y_1-Y_2)-Y'\rvert\) 回で移動することができます。 唯一の例外は、\(X_1-X_2=X'=0\) かつ \((Y_1-Y_2)\) と \(Y'\) の符号が異なる場合(制約よりこの場合\(Y_!-Y_2\neq 0, Y'\neq 0\) であることに注意)、あるいはその逆、\(Y_1-Y_2=Y'=0\) かつ \((X_1-X_2)\) と \(X'\) の符号が異なる場合です。この場合は原点を避けるために前者であれば \(X\) 方向、後者であれば \(Y\) 方向に余計に最低 \(2\) 回移動する必要があります。よって、この場合は \(\lvert (X_1-X_2)-X'\rvert+\lvert (Y_1-Y_2)-Y'\rvert+2\) 回となります。

ii) 訪れる必要のある地点が \(2\) つの場合 \(2\) つの地点は \((\pm 1,0)\) から \(1\) つ、 \((0, \pm 1)\) から \(1\) つ選ばれるため、どの \(2\) つの間も \(2\) 回で移動することができます。(逆に \(2\) 回は行動する必要があります。) よって高橋君は、訪れなければならない地点のうち初期位置から近い方の地点に移動し、その後 \(2\) 回移動すれば良いことがわかります。初期位置から各地点への移動に必要な行動回数は i) で求めているため、比較して小さい方に \(2\) (もう一方の訪れなければならない地点まで移動するための行動回数)を足せば良いです。

これで全ての場合について、答えを求めることができました。

c++ による実装例(詳細で述べられている方針に沿った実装例) :

#include <bits/stdc++.h>
using namespace std;

long long dist(long long x1,long long y1,long long x2,long long y2){
	if((x1==0)&&(x2==0)&&(signbit(y1)!=signbit(y2)))return abs(y1-y2)+2;
	if((y1==0)&&(y2==0)&&(signbit(x1)!=signbit(x2)))return abs(x1-x2)+2;
	return abs(x1-x2)+abs(y1-y2);
}

int main() {
	long long x[3],y[3];
	int idx=0;
	long long vis[2][2];

	cin>>x[0]>>y[0]>>x[1]>>y[1]>>x[2]>>y[2];
	x[0]-=x[1],y[0]-=y[1];
	x[2]-=x[1],y[2]-=y[1];

	if(x[2]>0){vis[idx][0]=-1,vis[idx][1]=0,idx++;}
	if(x[2]<0){vis[idx][0]=1,vis[idx][1]=0,idx++;}
	if(y[2]>0){vis[idx][0]=0,vis[idx][1]=-1,idx++;}
	if(y[2]<0){vis[idx][0]=0,vis[idx][1]=1,idx++;}

	long long ans=abs(x[2])+abs(y[2]);
	if(idx==1)ans+=dist(x[0],y[0],vis[0][0],vis[0][1]);
	else ans+=min(dist(x[0],y[0],vis[0][0],vis[0][1]),dist(x[0],y[0],vis[1][0],vis[1][1]))+2;

	cout<<ans<<endl;
	return 0;
}