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; }