TopCoder SRM 792 : Div1 Easy Div2 Hard TwoRobots

お、これでSRMタグの記事1000個目だ。
https://community.topcoder.com/stat?c=problem_statement&pm=16537&rd=18340

問題

グリッド上2体のロボットの初期位置とゴールが与えられる。
一部のセルはロボットが侵入不可である。

時間1毎にロボットは必ず隣接マスのいずれかに移動する。
その際、両ロボットが同じマスに来たり、入れ違いになるような移動の仕方は許容されない。
両者が同時にそれぞれのゴールに到着する最短時間はいくつか。

解法

マスが1600個しかないので、2体のロボットの位置を1600*1600通りBFSで探索すればよい。

int D[1600][1600];


class TwoRobots {
	public:
	int move(vector <string> plan) {
		int H,W,x,y;
		H=plan.size();
		W=plan[0].size();
		FOR(x,1600) FOR(y,1600) D[x][y]=1<<30;
		int X[4],Y[4];
		FOR(y,H) FOR(x,W) {
			if(plan[y][x]=='A') X[0]=x,Y[0]=y;
			if(plan[y][x]=='B') X[1]=x,Y[1]=y;
			if(plan[y][x]=='a') X[2]=x,Y[2]=y;
			if(plan[y][x]=='b') X[3]=x,Y[3]=y;
		}
		D[Y[0]*40+X[0]][Y[1]*40+X[1]]=0;
		queue<int> Q;
		Q.push((Y[0]*40+X[0])*1600+(Y[1]*40+X[1]));
		int i,j;
		while(Q.size()) {
			int ax=Q.front()/1600%40;
			int ay=Q.front()/(1600*40)%40;
			int bx=Q.front()%40;
			int by=Q.front()/40%40;
			int c=D[ay*40+ax][by*40+bx];
			Q.pop();
			if(ax==X[2]&&ay==Y[2]&&bx==X[3]&&by==Y[3]) return c;
			
			int d[4]={0,-1,0,1};
			FOR(i,4) FOR(j,4) {
				int Ax=ax+d[i];
				int Ay=ay+d[i^1];
				int Bx=bx+d[j];
				int By=by+d[j^1];
				if(Ax==Bx&&Ay==By) continue;
				if(Ax==bx&&Ay==by&&Bx==ax&&By==ay) continue;
				if(Ax<0||Bx<0||Ax>=W||Bx>=W) continue;
				if(Ay<0||By<0||Ay>=H||By>=H) continue;
				if(plan[Ay][Ax]=='#') continue;
				if(plan[By][Bx]=='#') continue;
				
				if(D[Ay*40+Ax][By*40+Bx]>c+1) {
					D[Ay*40+Ax][By*40+Bx]=c+1;
					Q.push((Ay*40+Ax)*1600+(By*40+Bx));
				}
			}
		}
		return -1;
		
	}
}

まとめ

正直面倒なだけで余り面白くない問題。