SRM 550 Div1 300 RotatingBot

2012-07-22

11:55 |

ロボットが長方形の壁の中のどこかにいて、東を向いていて、壁かすでに訪れたとこに当たったら左に回転する。動けなくなったらおわり。
連続して進んだ回数が配列 M で与えられるので、動いた範囲を含む長方形の面積の最小値をもとめる。ありえない場合は-1を返す
|M| in [1, 50], M の要素 in [1, 50]

|M|≦3のときは無矛盾。
|M|＞3のときは M[0]～M[3] で壁の幅と高さが決まる。
（M[0]～M[3]が正しくないとするとそもそもいずれM[0]～M[3]の動き検証で矛盾になるので正しいとしていい）
以降シミュレートして矛盾がないか確かめる。
最後以外は止まった時目の前に既に訪れたフラグがないとだめ

challenge phase
n≧3 のときにM[0]≧M[2]なら矛盾としてるコードを見つけたので 10 6 3 的な無矛盾のテストを投げたところ失敗 -25
実際のところ n＞3 と書いてあって、投げる0.2秒くらい前にいや n＞3 と書いてあるぞなんか変だぞと思ったが右人差し指を止めることはできなかった orz
チャレンジは焦るべからずってどっかに書いておこうかなｗ

passes system test

class RotatingBot {
	public:
	int minArea(vector <int> M) {
		ll N=M.size();
		if(N==1) return M[0]+1;
		if(N==2) return (M[0]+1)*(M[1]+1);
		if(N==3) return max(M[0]+1, M[2]+1)*(M[1]+1);
		ll W=max(M[0]+1, M[2]+1);
		ll H=max(M[1]+1, M[3]+1);
		ll sX = W-M[0]-1;
		ll sY = M[1];
		VVI w(H+2, VI(W+2));
		REP(x, W+2) w[0][x]=w[H+1][x]=1;
		REP(y, H+2) w[y][0]=w[y][W+1]=1;
		w[sY+1][sX+1]=1;
		int dx[4]={1,0,-1,0};
		int dy[4]={0,-1,0,1};
		REP(i, N) {
			int dir=i%4;
			REP(j, M[i]) {
				sX += dx[dir];
				sY += dy[dir];
				if(w[sY+1][sX+1]) return -1;
				w[sY+1][sX+1]=1;
			}
			if(i!=N-1 && w[sY+dy[dir]+1][sX+dx[dir]+1]==0) return -1;
		}
		return W*H;
	}
};