Turn over game

 avatar
quoc14
c_cpp
5 months ago
5.4 kB
3
Indexable
Backtrack
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