UVa-10309 : Turn the Lights Off

問題概要

サイズ10*10のライツアウトを解いて最小手順を答える。

解法

このサイズなら全探索。(サイズが大きくなったら連立一次方程式を考える)

acceptされたコード

計算量O(2^W*W^2)。

#include <cstdio>
#include <cstring>
using namespace std;

const int W = 10;
const int INF = 1<<29;

char board[W][W+1];
char name[257];

bool on[W][W];

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

void init(){
	for(int i=0; i<W; i++){
		scanf("%[^\n]%*c", board[i]);
	}
}

void turn(int y, int x){
	for(int k=0; k<5; k++){
		int ny = y + dy[k], nx = x + dx[k];
		if(0<=ny && ny<W && 0<=nx && nx<W){
			on[ny][nx] = !on[ny][nx];
		}
	}
}

int solve(){
	int ans = INF;

	for(int bit=0; bit<(1<<W); bit++){
		int cnt = __builtin_popcount(bit);
		for(int i=0; i<W; i++){
			for(int j=0; j<W; j++){
				on[i][j] = board[i][j] == 'O';
			}
		}

		for(int i=0; i<W; i++)if( (bit>>i)&1 ){
			turn(0, i);
		}

		for(int i=1; i<W; i++){
			for(int j=0; j<W; j++)if( on[i-1][j] ){
				cnt++;
				turn(i, j);
			}
		}

		bool is_on = false;
		for(int i=0; i<W; i++){
			is_on |= on[W-1][i];
		}

		if(!is_on && cnt < ans){
			ans = cnt;
		}
	}

	return ans;
}

int main(){
	while(scanf("%[^\n]%*c", name), strcmp(name, "end")){
		init();
		int ans = solve();
		if(ans > 100){
			ans = -1;
		}
		printf("%s %d\n", name, ans);
	}
	return 0;
}