AOJ 0236 - Alien Messages

問題文 : 宇宙人のきまぐれメッセージ

解法 :
6 つの接続可能性をすべてのマスについて試すO(6^(W*H)) 通りの探索と, それが終わったあとに接続関係が適切であるかをWF で確かめるO((W*H)^3)を掛け合わせてO(6^(W*H)*(W*H)^3) という絶望的な最悪計算量だが,

・左/上のマスと接続される必要があればかならず接続されている状態にのみ遷移する.
・壁/場面外と接続される場合は遷移をしない.

という2 つの枝刈りを行うことでAC することが可能である.

接続可能性のチェックはBFS でもよさそうなので, O((W*H)^2) 分の高速化が期待できる...かもしれない.

コード :

#include <cstdio>
#include <cstring>

using namespace std;

int dy[] = {1, -1, 0, 0};
int dx[] = {0, 0, 1, -1};

bool mv[10][4] = {{1, 0, 0, 0},
				 {0, 1, 0, 0},
				 {0, 0, 1, 0},
				 {0, 0, 0, 1},
				 {1, 0, 1, 0},
				 {1, 0, 0, 1},
				 {0, 1, 1, 0},
				 {0, 1, 0, 1},
				 {1, 1, 0, 0},
				 {0, 0, 1, 1}};

int w, h;
int board[8][8], state[8][8];
bool con[49][49];

bool check()
{
	memset(con, 0, sizeof(con));
	for (int i = 0; i < h; i++){
		for (int j = 0; j < w; j++){
			for (int k = 0; k < 4; k++){
				if (~state[i][j] && mv[state[i][j]][k] && ~state[i + dy[k]][j + dx[k]])
					con[i * w + j][(i + dy[k]) * w + j + dx[k]] = con[(i + dy[k]) * w + j + dx[k]][i * w + j] = true;
			}
		}
	}
	for (int k = 0; k < w * h; k++)
		for (int i = 0; i < w * h; i++)
			for (int j = 0; j < w * h; j++)
				con[i][j] |= (con[i][k] & con[k][j]);
	for (int i = 0; i < w * h; i++){
		for (int j = 0; j < w * h; j++){
			if (~state[i / w][i % w] && ~state[j / w][j % w] && !con[i][j]) return (false);
		}
	}
	return (true);
}

bool check(int npos)
{
	if (npos == w * h){
		return (check());
	}
	
	int ny = npos / w, nx = npos % w;
	if (0) printf("ny = %d nx = %d\n", ny, nx);
	if (!board[ny][nx]) return (check(npos + 1));
	
	for (int i = 4; i < 10; i++){
		state[ny][nx] = i;
		for (int j = 0; j < 4; j++) if (mv[i][j] &&
										(!(0 <= ny + dy[j] && ny + dy[j] < h && 0 <= nx + dx[j] && nx + dx[j] < w) ||
										 !board[ny + dy[j]][nx + dx[j]])) goto ng;
		if (mv[i][1] && !(state[ny - 1][nx] == 0 || state[ny - 1][nx] == 4 || state[ny - 1][nx] == 5 || state[ny - 1][nx] == 8)) goto ng;
		if (ny > 0 && !mv[i][1] && (state[ny - 1][nx] == 0 || state[ny - 1][nx] == 4 || state[ny - 1][nx] == 5 || state[ny - 1][nx] == 8)) goto ng;
		if (mv[i][3] && !(state[ny][nx - 1] == 2 || state[ny][nx - 1] == 4 || state[ny][nx - 1] == 6 || state[ny][nx - 1] == 9)) goto ng;
		if (nx > 0 && !mv[i][3] && (state[ny][nx - 1] == 2 || state[ny][nx - 1] == 4 || state[ny][nx - 1] == 6 || state[ny][nx - 1] == 9)) goto ng;
		if (check(npos + 1)) return (true);
		ng:;
		state[ny][nx] = -1;
	}
	
	return (false);
}

int main()
{
	while (scanf("%d %d", &w, &h) && w){
		int count = 0;
		for (int i = 0; i < h; i++){
			for (int j = 0; j < w; j++){
				scanf("%d", &board[i][j]);
				board[i][j] ^= 1;
				state[i][j] = -1;
				count += board[i][j];
			}
		}
		printf("%s\n", count && check(0) ? "Yes" : "No");
	}
	
	return (0);
}