Google Code Jam 2014 Qualification Round : C. Minesweeper Master

段々難易度が上がってきた。Smallで数回Incorrectな回答をしてしまった。
https://code.google.com/codejam/contest/2974486/dashboard#s=p2

問題

パラメータR,C,Mが与えられる。
RxCのフィールドで構築されたマインスイーパのフィールドに対し、M個爆弾を配置したい。

通常のマインスイーパ同様、クリックした位置の周囲８マスに爆弾がない場合、連鎖的にそれらのマスを自動で開きに行く。
Mがわかっている場合、最初のクリックでM個の爆弾の位置をすべて特定できるような爆弾配置が可能ならそれを答えよ。

解法

M個がすべて特定できるということは、逆に爆弾のないマスL=R*C-M個を最初のクリックですべて開けることを意味する。

• L=1の場合、そこをクリックすれば他は全部爆弾なのでそこを１クリックすればよい。
• R=1またはC=1、すなわち１行か１列の場合、端から爆弾を埋めていって反対側の端をクリックすればよい。

問題は残りの場合である。
いずれも左上のマスをクリックすることとして、以下のいずれかを満たせば条件を満たせる。

• 空きマスが2以上の整数X,YでL=X*Yで表せる場合。
  • この時は以下のように左上X*Yマス分空きマスを配置すればよい。

c...**
....**
....**
******

• 空きマスが2以上の整数X,Y,PでL=X*Y+P (P
  • この時は以下のように左上X*Yマス分空きマスを配置し、(Y+1)行目に残りP個を配置すればよい。
  • 縦横逆のケースも同様に試せる。

c...**
....**
....**
..****
******

• 上のパターンでP==1なら満たせる場合、Y行目を1個欠けさせてY+1行目を１個増やす。
  • ただしY>2でないとこのパターンは無理。

c....*
.....*
.....*
.....*
....**
..****
******

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	char hoge[51][51];
	int R,C,M,L;
	
	cin>>R>>C>>M;
	L=R*C-M;
	
	ZERO(hoge);
	FOR(y,R) FOR(x,C) hoge[y][x]='*';
	
	_P("Case #%d:\n",_loop);
	
	if(L==1) {
		hoge[0][0]='c';
		FOR(y,R) _P("%s\n",hoge[y]);
		return;
	}
	else if(R==1) {
		if(M>=C-1) _P("Impossible\n");
		else {
			FOR(i,M) _P("*");
			FOR(i,C-1-M) _P(".");
			_P("c\n");
		}
	}
	else if(C==1) {
		if(M>=R-1) _P("Impossible\n");
		else {
			FOR(i,M) _P("*\n");
			FOR(i,R-1-M) _P(".\n");
			_P("c\n");
		}
	}
	else {
		if(L<=3) _P("Impossible\n");
		else {
			
			int CC,RR,ok=0;;
			for(RR=2;RR<=R;RR++) for(CC=2;CC<=C;CC++) {
				if(RR*CC==L) {
					FOR(y,RR) FOR(x,CC) hoge[y][x]='.';
					ok=1;
				}
				else if(RR*CC<=L && RR<R && (RR+1)*CC>L && L%CC>1 && RR>1) {
					FOR(y,RR) FOR(x,CC) hoge[y][x]='.';
					FOR(x,L%CC) hoge[RR][x]='.';
					ok=1;
				}
				else if(RR*CC<=L && RR<R && (RR+1)*CC>L && L%CC==1 && RR>2 && CC>2) {
					FOR(y,RR) FOR(x,CC) hoge[y][x]='.';
					hoge[RR-1][CC-1]='*';
					hoge[RR][0]=hoge[RR][1]='.';
					ok=1;
				}
				else if(RR*CC<=L && CC<C && (CC+1)*RR>L && L%RR>1 && CC>1) {
					FOR(y,RR) FOR(x,CC) hoge[y][x]='.';
					FOR(y,L%RR) hoge[y][CC]='.';
					ok=1;
				}
				else if(RR*CC<=L && CC<C && (CC+1)*RR>L && L%RR==1 && CC>2 && RR>2) {
					FOR(y,RR) FOR(x,CC) hoge[y][x]='.';
					hoge[RR-1][CC-1]='*';
					hoge[0][CC]=hoge[1][CC]='.';
					ok=1;
				}
				if(ok) {
					hoge[0][0]='c';
					FOR(y,R) _P("%s\n",hoge[y]);
					return;
				}
			}
			_P("Impossible\n");
		}
	}
	
	
}

まとめ

なんか場合分けが面倒な感じ。
もっときれいに書けないかな。