Untitled
unknown
plain_text
a year ago
4.3 kB
10
Indexable
Never
Turn Over Game As in , there is a 4×4 sized table. In a grid of the table, there are white or black stones. When you choose a position of stone randomly, the stone and four stones adjacent to the up, down, left and right sides of the stone will turn to the opposite color like turning a white stone to a black & a black stone to a white. Let’s suppose this process as a calculation. Using such a calculation, you want to change all the stones on the table into all whites or all blacks. Find out the minimum operation count at this time. Time limit: 1 second (java: 2 seconds) [Input] Several test cases can be included in the inputs. T, the number of cases is given in the first row of the inputs. After that, the test cases as many as T (T ≤ 30) are given in a row. Table info is given without blank over four rows per each test case. Colors are indicated like white for ‘w’ and black for ‘b’. [Output] Output the minimum operation count to change all colors as white or black on the first row per each test case. If not possible, output "impossible" . [I/O Example] Input 2 bwwb bbwb bwwb bwww bwbw wwww bbwb bwwb Output Case #1 4 Case #2 impossible testttttttttt case 50 wbwb wbbw wbww wbww bbwb bbbw wbww bwwb bbbb wwbw bwbb bbbb bwwb bwww wwbb wbbb wbbb bbww bbwb wwbw wbwb bwww bwbw wwbw wbww wbww bbbw bwwb wbbw wbwb bbbb wbww wbww wbwb wwww bwwb bwwb bbww bwww bbbw bwbw wwbw wwww wbww bwbb bwww bwbb wwww wbbw bbbb bwww bbww wbwb bwbw bwbw bwbw bbww bbwb bbbw wwwb bwbb wbbw wwww bwbb bbww wbbw bbbw wbbw bwbb bbww wbww wbbb bwwb bbww wwww wwbw bbbb bwbb wwww bwww bwbw wwbw wwbb wwww bwww bwbb bbwb wwwb wwww bwbw bbbb wbww bwbb wwwb wbww bwwb bwww bbwb wwbb bbwb wbww bwww wbww bwwb bwbb wbbw bwwb wbww bbbw wwww wwbw wbbw wwbw bbbw bwwb wbbb bwbw bwbb bbwb bwbw bwww wwww bbbw wwbw wbww wbww wbbb wbbw bbbb wwww bbbb bwwb wwww wbwb wbwb bwwb bbwb bbww bbbb bwwb wwww wwbb wbbw wbww bbwb wwww wwww wwww wwww wwww bwbb bbww bwbb wwww wbbb bwww bwbw wwbb wbww bbbb bwww wbwb wwbb wbbb wbww wwbb bbbw wbwb wwwb bbbw bwww wwwb bwbb bwbb wwww wbwb wbbw bwwb bbbw bbww wbwb bwbw wwbb wbwb bwbb bbbb wbwb bwwb bwbw bwwb bwbw bwww bwbw wwww bbwb bwwb bbbb bbbb bbbb bbbb ket qua Case #1 5 Case #2 3 Case #3 3 Case #4 5 Case #5 5 Case #6 5 Case #7 4 Case #8 3 Case #9 6 Case #10 4 Case #11 4 Case #12 3 Case #13 5 Case #14 5 Case #15 5 Case #16 5 Case #17 5 Case #18 5 Case #19 5 Case #20 2 Case #21 4 Case #22 6 Case #23 3 Case #24 5 Case #25 3 Case #26 5 Case #27 5 Case #28 4 Case #29 4 Case #30 5 Case #31 4 Case #32 4 Case #33 4 Case #34 3 Case #35 4 Case #36 3 Case #37 impossible Case #38 impossible Case #39 4 Case #40 4 Case #41 2 Case #42 5 Case #43 5 Case #44 3 Case #45 3 Case #46 5 Case #47 5 Case #48 4 Case #49 impossible Case #50 0 code #include<iostream> using namespace std; int arr[4][4]; int dx[4]= {-1,0,0,1}; int dy[4]= {0,-1,1,0}; int m=1000000; void lat(int x, int y){ arr[x][y]= 1- arr[x][y]; for(int i=0;i<4;i++){ int tempx= x+dx[i]; int tempy= y+dy[i]; if(tempx>=0 && tempx<4 && tempy >= 0 && tempy<4){ arr[tempx][tempy]= 1- arr[tempx][tempy]; } } } bool check(){ int num= arr[0][0]; for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ if(arr[i][j]!=num)return false; } } return true; } void Try(int x, int y,int step){ if(check()){ if(step<m){ m=step; } return; } if(x>=4)return; if(step>m){ return; } if(y+1<4){ lat(x,y); Try(x, y+1,step+1); lat(x,y); Try(x, y+1,step); } else{ lat(x,y); Try(x+1, 0,step+1); lat(x,y); Try(x+1, 0,step); } } int main(){ //freopen("input.txt","r",stdin); int t; cin>>t; for(int i=1;i<=t;i++){ char x; for(int h=0;h<4;h++){ for(int k=0;k<4;k++){ cin>>x; arr[h][k] = (x=='w')?0:1; } } m=1000000; Try(0,0,0); cout<<"Case #"<<i<<endl; if(m==1000000){ cout<<"impossible"<<endl; } else cout<<m<<endl; } return 0; }