TopCoder SRM 826 : Div1 Medium TwoCatsAndAMouse

これ珍しい出力形式だな。
https://community.topcoder.com/stat?c=problem_statement&pm=17479

問題

R*Cのグリッド上に、2匹の猫と1匹のネズミがいるものとする。
猫とネズミは交互にターンがやってきて移動する。
いずれも、自身のターンではその位置にとどまるか隣接マスに移動するかを選択できる。
2匹の猫は同じセルに存在してもよい。

いずれかの猫がネズミと同じマスに到達したら猫の勝利とする。
R≧Cの時、猫とネズミ合わせて(4R+2C)ターン以内に猫が勝利できるよう、猫の移動方法を決めたい。
猫とネズミの所在全パターンに対し、猫の移動方法を答えよ。

解法

1匹目の猫は行を合わせたのち列を、2匹目はその逆順で合わせればよい。

両猫は、まず(R-1)ターン以内にそれぞれ行・列をネズミと同じかその隣に合わせることができる。
以後、ネズミが列と行どちらをずらしても、両猫の片方はネズミとの距離を詰められる。
なので、2(R+C)ターン以内にどちらかの猫はネズミのマスに到達する。

class TwoCatsAndAMouse {
	public:
	string catchMouse(int R, int C) {
		int cy1,cy2,my;
		int cx1,cx2,mx;
		string S;
		FOR(cy1,R) FOR(cx1,C) FOR(cy2,R) FOR(cx2,C) FOR(my,R) FOR(mx,C) {
			int p1=0;
			int p2=0;
			
			//c1は先にy
			if(cy1<my) p1=2;
			else if(cy1>my) p1=1;
			else if(cx1<mx) p1=4;
			else if(cx1>mx) p1=3;
			else continue;
			//c2は先にx
			if(cx2<mx) p2=4;
			else if(cx2>mx) p2=3;
			else if(cy2<my) p2=2;
			else if(cy2>my) p2=1;
			else continue;
			
			int ch=65+p1*5+p2;
			S.push_back(ch);
			
		}
		
		return S;
	}
}

まとめ

本番これ即思いついたんだけど、他の人全然submitしてないし、不安になって余計な判定ルーチン入れたりタイムロスしてしまった。
もったいなかったな…。