AOJ1158 ICPC: Intelligent Congruent Partition of Chocolate

問題リンク ICPC: Intelligent Congruent Partition of Chocolate

• 解法

チョコレートの総数をNとします。チョコのグループをAとBと呼びます。Aのチョコレートに所属するチョコをN/2個決めたら、AとBのチョコレートがそれぞれ連結しているか調べて解とします。
普通にチョコの所属を考えると、combi(N, N/2)でえっらいことになるので工夫します。
チョコは回転、移動、裏返しができます。チョコが合同になるとき、その重なり方がどうなるかを先に決めます。回転は4方向、移動は最大35通り、裏返しは2通りあります。この重なり方を決め、チョコの始点をA(si, sj), B(ti, tj)とし、この2点が重ね合わせた時に被さるものと考えます。すると、(i, j)のチョコをAに採用したときに、これはBの始点から考えてどこにあるかは計算で求まります。計算した座標が既にAかBに採用されていたり、チョコが無かったりすれば失敗として枝刈りします。
この探索の方法だとまだTLEが取れないと思うので更に工夫を施します。
自分はAとして採用するチョコを再帰関数によって、左上から右下の方向へ考えています。
残りの部分にあるチョコを全てとってもN/2個に届かない場合は枝刈りします。
更に、これまで採用したチョコで孤立しているチョコがあれば連結にならないので枝刈りしています。この2つを入れておくと解けます。
あとNが奇数だったら問答無用でNOです

• ソース

import java.util.Arrays;
import java.util.Scanner;

//ICPC: Intelligent Congruent Partition of Chocolate
public class AOJ1158 {

	int w, h, si, sj, ti, tj, N, c;
	int[][] a;
	int[] sum;
	boolean[][] u;
	int[][] d = {{-1,0},{0,1},{1,0},{0,-1}};

	boolean cancel(int t){
		if(t<0)return false;
		int i = t/w, j = t%w;
		if(a[i][j]!=-1)return false;
		int cnt = 0;
		for(int k=0;k<4;k++){
			int ni = i+d[k][0], nj = j+d[k][1];
			if(0<=ni&&ni<h&&0<=nj&&nj<w&&a[ni][nj]==-1)cnt++;
		}
		return cnt==0;
	}
	
	boolean dfs(int i, int j, int rot, int rev, int num){
		if(num==(N>>1)){
			for(boolean[]v:u)Arrays.fill(v, false);
			c = 0;
			check(si, sj, -1);
			if(c!=(N>>1))return false;
			c = 0;
			check(ti, tj, -2);
			return c==(N>>1);
		}
		if(i==h || (N>>1)-num > sum[i*w+j] || cancel(i*w+j-w-1))return false;
		if(j==w)return dfs(i+1, 0, rot, rev, num);
		if(a[i][j]==1){
			a[i][j] = -1;
			int di = i-si, dj = j-sj;
			int ni, nj;
			if(rot==0){
				ni = di; nj = dj;
			}
			else if(rot==1){
				ni = dj; nj = -di;
			}
			else if(rot==2){
				ni = -di; nj = -dj;
			}
			else{
				ni = -dj; nj = di;
			}
			if(rev==1)nj*=-1;
			int ki = ti+ni, kj = tj+nj;
			if(0<=ki&&ki<h&&0<=kj&&kj<w&&a[ki][kj]==1){
				a[ki][kj] = -2;
				if(dfs(i, j+1, rot, rev, num+1))return true;
				a[ki][kj] = 1;
			}
			a[i][j] = 1;
		}
		return dfs(i, j+1, rot, rev, num);
	}
	
	void check(int i, int j, int x){
		if(u[i][j])return;
		u[i][j] = true;
		c++;
		for(int k=0;k<4;k++){
			int ni = i+d[k][0], nj = j+d[k][1];
			if(ni < 0 || h <= ni || nj < 0 || w <= nj || a[ni][nj]!=x)continue;
			check(ni, nj, x);
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			w = sc.nextInt(); h = sc.nextInt();
			if((w|h)==0)break;
			N = 0;
			a = new int[h][w];
			u = new boolean[h][w];
			sum = new int[h*w+1];
			si = sj = -1;
			for(int i=0;i<h;i++)for(int j=0;j<w;j++){
				a[i][j] = sc.nextInt();
				if(a[i][j]==1){
					N++;
					if(si==-1){
						si = i; sj = j;
					}
				}
			}
			if((N&1)==1){
				System.out.println("NO"); continue;
			}
			for(int i=h-1;i>=0;i--)for(int j=w-1;j>=0;j--)sum[i*w+j] = sum[i*w+j+1]+a[i][j];
			boolean res = false;
			a[si][sj] = -1;
			for(int i=0;i<h;i++)for(int j=0;j<w;j++)if(a[i][j]==1){
				ti = i; tj = j;
				a[i][j] = -2;
				for(int rot=0;rot<4;rot++)for(int rev=0;rev<2;rev++){
					if(dfs(0, 0, rot, rev, 1)){
						res = true;
					}
					if(res)break;
				}
				a[i][j] = 1;
			}
			System.out.println(res?"YES":"NO");
		}
	}
	
	public static void main(String[] args) {
		new AOJ1158().run();
	}
}