Untitled
unknown
plain_text
2 years ago
1.5 kB
4
Indexable
#include<iostream> using namespace std; char a[4][4]; int b[4][4]; int ans; int dx[] = { 1, -1, 0, 0 }; int dy[] = { 0, 0, 1, -1 }; bool checkColor() { int sum = 0; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { sum += b[i][j]; } } if (sum == 16 || sum == 0) return true; return false; } void changeColor(int x, int y) { b[x][y] = 1 - b[x][y]; for (int i = 0; i < 4; i++) { int xx = x + dx[i]; int yy = y + dy[i]; if (xx >= 0 && xx < 4 && yy >= 0 && yy < 4) { b[xx][yy] = 1 - b[xx][yy]; } } } void backTrack(int x, int y, int count) { if(checkColor()){ if (count < ans) { ans=count; } return; } if(x>=4) return; if(count > ans) return; if(y+1<4){ changeColor(x,y); backTrack(x,y+1, count+1); changeColor(x,y); backTrack(x,y+1, count); } else{ changeColor(x,y); backTrack(x+1,0, count+1); changeColor(x,y); backTrack(x+1,0, count); } } int main(){ int test; cin >> test; for(int tc=1; tc <=test; tc++){ for(int i =0; i<4; i++){ for(int j=0; j<4; j++){ cin >> a[i][j]; } } for(int i =0; i<4; i++){ for(int j=0; j<4; j++){ if(a[i][j] == 'b') b[i][j] =1; else if(a[i][j] == 'w') b[i][j] =0; } } ans = 100000000; backTrack(0,0,0); cout <<"Case #" << tc <<endl; if(ans == 100000000) cout << "impossible" << endl; else cout << ans <<endl; } return 0; }
Editor is loading...