Turn over game
Level 4 Turn Over Game Như trong, có một cái bàn kích thước 4×4. Trong một lưới của bàn, có những viên đá màu trắng hoặc đen. Khi bạn chọn một vị trí của viên đá ngẫu nhiên, viên đá và bốn viên đá liền kề với các mặt trên, dưới, trái và phải của viên đá sẽ chuyển sang màu đối diện giống như biến một viên đá trắng thành đen và một viên đá đen thành trắng. Giả sử quá trình này như một phép tính. Sử dụng phép tính như vậy, bạn muốn đổi tất cả các viên đá trên bàn thành toàn màu trắng hoặc toàn màu đen. Tìm số lượng thao tác tối thiểu tại thời điểm này. Giới hạn thời gian: 1 giây (java: 2 giây) [Đầu vào] Có thể bao gồm một số trường hợp thử nghiệm trong các đầu vào. T, số lượng trường hợp được đưa ra trong hàng đầu tiên của các đầu vào. Sau đó, các trường hợp thử nghiệm nhiều nhất là T (T ≤ 30) được đưa ra trong một hàng. Thông tin bảng được đưa ra mà không có khoảng trắng trên bốn hàng cho mỗi trường hợp thử nghiệm. Màu sắc được chỉ định như màu trắng cho 'w' và màu đen cho 'b'. [Đầu ra] Đầu ra số lượng thao tác tối thiểu để thay đổi tất cả các màu thành trắng hoặc đen trên hàng đầu tiên cho mỗi trường hợp thử nghiệm. Nếu không thể, đầu ra "impossible". [I/O Example] Input 2 bwwb bbwb bwwb bwww bwbw wwww bbwb bwwb Output Case #1 4 Case #2 impossible 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 Time: 1.771000000 s. 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 #include <iostream> #include <time.h> using namespace std; int oo = 2000000000; int T, n = 4, result, mp[4][4]; int dx[5] = {0, -1, 1, 0, 0}; int dy[5] = {0, 0, 0, -1, 1}; bool inSide(int x, int y){ return x >= 0 & y >= 0 && x < n && y < n; } bool checkFull(){ int w = 0, b = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(mp[i][j]) b++; else if(!mp[i][j]) w++; } } return b == n*n || w == n*n; } void flip(int x, int y){ for(int d = 0; d < 5; d++){ int xx = x + dx[d]; int yy = y + dy[d]; if(inSide(xx, yy)){ mp[xx][yy] = 1 - mp[xx][yy]; } } } void backtrack(int X, int Y, int cnt){ int k = X * n + Y; if(k == n*n ){ if(checkFull()){ if(result > cnt){ result = cnt; return; } } return; } k++; int xx = k/n; int yy = k%n; for(int choose = 0; choose < 2; choose++){ if(choose){ flip(X, Y); backtrack(xx, yy, cnt + 1); flip(X, Y); } else{ backtrack(xx, yy, cnt); } } } int main(){ freopen("input.txt", "r", stdin); // Calc clock clock_t time_start, time_end; time_start = clock(); cin >> T; for(int tc = 1; tc <= T; tc++){ // Initial && Input result = oo; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ char c; cin >> c; if(c == 'b') mp[i][j] = 1; else if(c == 'w') mp[i][j] = 0; } } // Solve Problem backtrack(0, 0, 0); // Output cout << "Case #" << tc << endl; if(result == oo) cout << "impossible\n"; else cout << result << endl; } // Calc Time time_end = clock(); cout.setf(ios::fixed); cout.precision(9); cout << "Time: " << double (time_end - time_start) / double (CLOCKS_PER_SEC) << " s." << endl; return 0; }
Leave a Comment