AtCoder ABC #271 (京セラプログラミングコンテスト2022) : Ex - General General

場合分けが正解か…。
https://atcoder.jp/contests/abc271/tasks/abc271_h

問題

2次元座標において、8近傍の格子点のうち移動可能な向きが指定される。
(0,0)にある点を(A,B)に動かすのに必要な最小移動回数を求めよ。

解法

まず、最適手は以下のいずれかである。

• 移動しない(A=B=0の場合)
• 1種類の移動を使う
• 2種類の移動を使う
• 3種類の移動を使う。この時、斜め2通りのほか、上下左右のいずれかを1手だけ使う

対称性より、移動可能な向きと(A,B)を90度ずつ回転させながら行うと1/4のパターンだけ列挙すればよい。
具体的には以下を用いる。

• 1種類の移動を使う
  • 右移動だけ使う
  • 右上移動だけ使う
• 2種類の移動を使う
  • 右移動と下移動だけ使う
  • 右移動と斜め移動1種だけ使う
• 3種類の移動を使う
  • 上下左右の1手の移動は総当たりしつつ、斜め方向の移動2種を総当たりする

int T;
ll A,B;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>A>>B>>S;
		FORR(c,S) c-='0';
		ll ret=1LL<<60;
		if(A==0&&B==0) ret=0;
		FOR(i,4) {
			
			if(S[0]&&A>0&&B==0) chmin(ret,abs(A));
			if(S[1]&&A>0&&A==B) chmin(ret,abs(A));
			if(S[0]) {
				if(S[1]&&A>=0&&B>=0&&B<=A) chmin(ret,abs(A));
				if(S[2]&&A>=0&&B>=0) chmin(ret,abs(A)+abs(B));
				if(S[3]&&B>=0&&A+B>=0) chmin(ret,abs(B)+abs(A+B));
				if(S[5]&&B<=0&&A>=B) chmin(ret,abs(B)+abs(A-B));
				if(S[7]&&A>=0&&B<=0&&abs(A)>=abs(B)) chmin(ret,abs(A));
			}
			if(S[1]&&S[3]&&B>0&&abs(A)<=abs(B)&&(A+B)%2==0) chmin(ret,abs(B));
			
			int dx[4]={1,0,-1,0};
			int dy[4]={0,1,0,-1};
			FOR(j,4) if(S[j*2]) {
				ll A2=A-dx[j];
				ll B2=B-dy[j];
				if((A2+B2)%2) continue;
				if(S[1]&&S[3]&&B2>=0&&abs(A2)<=abs(B2)) chmin(ret,abs(B2)+1);
				if(S[1]&&S[7]&&A2>=0&&abs(A2)>=abs(B2)) chmin(ret,abs(A2)+1);
				if(S[5]&&S[3]&&A2<=0&&abs(A2)>=abs(B2)) chmin(ret,abs(A2)+1);
				if(S[5]&&S[7]&&B2<=0&&abs(A2)<=abs(B2)) chmin(ret,abs(B2)+1);
			}
			
			
			swap(A,B);
			B=-B;
			rotate(S.begin(),S.begin()+2,S.end());
		}
		
		if(ret==1LL<<60) ret=-1;
		cout<<ret<<endl;
	}
}

まとめ

本番は座標圧縮で頑張ろうとしたが、さっさと場合分けすればよかったか…。