TurnOverGame
ptrdung
plain_text
a year ago
3.9 kB
8
Indexable
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. [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 #include<iostream> using namespace std; int Answer[25]; int chess[8][8]; int num = 0; int maximum = 0; int visited[8][8]; int checkQueen(int x, int y) { for(int i = 0; i < x; i++) { for(int j = 0; j < 8; j++) { if( (j == y) || ((i + j) == (x + y)) || ((i -j ) == (x-y)) ) { if(visited[i][j] == 1) return 0; } } } return 1; } void BT(int x, int y, int temp) { if(x == 7) //cuối bàn cờ { temp += chess[x][y]; if(temp > maximum) maximum = temp; return; } temp += chess[x][y]; visited[x][y] = 1; for(int i = 0; i < 8; i++) { if(checkQueen(x+1, i)) BT(x+1, i, temp); } //temp -= chess[x][y]; visited[x][y] = 0; } int main(int argc, char** argv) { int test_case; int T; ios::sync_with_stdio(false); freopen("input.txt", "r", stdin); cin >> T; for(test_case = 1; test_case <= T; ++test_case) { for(int i = 0; i < 25; i++) Answer[i] = 0; cin >> num; for(int q = 0; q < num; q++) { for(int i = 0; i < 8; i++) for (int j = 0; j < 8; j++) cin >> chess[i][j]; maximum = 0; for(int i = 0; i < 8; i++) { for(int j = 0; j < 8; j++) visited[i][j] == 0; } for(int i = 0; i < 8; i++) BT(0, i, 0); Answer[q] = maximum; } cout << "Case #" << test_case << endl; for(int i = 0; i < num; i++) { cout << Answer[i] << endl; } // cần phần in ra output :))) //cout << "#" << test_case << " " << Answer << endl; } return 0; } 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
Editor is loading...
Leave a Comment