Untitled
user_1164828
plain_text
a month ago
1.3 kB
0
Indexable
Never
///Turn over game #include<iostream> using namespace std; char map[10][10]; int cnt; int ans; int n = 4; int dx[] = {1,0,0,-1}; int dy[] = {0,1,-1,0}; bool check(){ int w = 0, b =0; for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ if(map[i][j] =='w') w++; else b++; } } return w == n*n || b == n*n; } void changeColor(int r, int c){ if(map[r][c] == 'w'){ map[r][c] = 'b'; } else map[r][c] = 'w'; int xN, yN; for(int i=0; i<4; i++){ xN = r + dx[i]; yN = c + dy[i]; if(xN >= 0 && xN <= n-1 && yN >=0 && yN <=n-1){ if(map[xN][yN] == 'w'){ map[xN][yN] = 'b'; } else{ map[xN][yN] = 'w'; } } } } int min(int x, int y){ return (x<y) ? x : y; } void BT(int k, int cnt){ if (check()){ ans = min(ans, cnt); } if(cnt >= ans) return; if(k==16) return; for(int i=0; i<2; i++){ if (i==1){ changeColor(k/n,k%n); BT(k+1,cnt+1); changeColor(k/n,k%n); } else{ BT(k+1,cnt); } } } int main(){ //freopen("Text.txt", "r", stdin); int T; cin >> T; for(int tc = 1; tc<=T; tc++){ for(int i=0; i<n; i++){ cin >> map[i]; } cnt = 0; ans = 1000000; BT(0,0); cout << "Case #" << tc << endl; if(ans == 1000000){ cout << "impossible" << endl; } else cout<< ans << endl; } return 0; }
Leave a Comment