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
Code Solution:
package practice;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class TurnOverGame {
Scanner sc = new Scanner(System.in);
int t;
String s;
int map[][];
int ans;
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
void init() {
map = new int[4][4];
ans = 20;
}
boolean checkColor() {
int sum = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
sum += map[i][j];
}
}
if (sum == 16 || sum == 0)
return true;
return false;
}
void changeColor(int x, int y) {
map[x][y] = 1 – map[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) {
map[xx][yy] = 1 – map[xx][yy];
}
}
}
void backTracking(int index, int count) {
if (count >= ans) { // này viết lộn chỗ này
return;
}
if (index == 16) {
if (checkColor() == true) {
if (count < ans) {
ans = count;
}
}
return;
}
// khong lat mau
backTrack(index + 1, count);
// lat mau
int x = index / 4;
int y = index % 4;
changeColor(x, y);
backTrack(index + 1, count + 1);
changeColor(x, y);
}
// copy sửa lại mà AC chứng tỏ hàm backTrack ở trên mình viết sai chỗ nào đó
void backTrack(int index, int count) {
if (count >= ans) {
return;
}
if (index == 16) {
if (checkColor() == true) {
ans = count;
}
return;
}
backTrack(index + 1, count);
// lat mau
int x = index / 4;
int y = index % 4;
changeColor(x, y);
backTrack(index + 1, count + 1);
changeColor(x, y);
}
void solution() {
t = sc.nextInt();
sc.nextLine();
for (int tc = 1; tc <= t; tc++) {
init();
for (int i = 0; i < 4; i++) {
s = sc.nextLine();
for (int j = 0; j < s.length(); j++) {
if (s.charAt(j) == ‘b’) {
map[i][j] = 1;
}
}
}
// backTrack(0, 0);
backTracking(0, 0);
System.out.println(“Case #” + tc);
if (ans != 20) {
System.out.println(ans);
} else {
System.out.println(“imposible”);
}
}
}
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream(“TurnOverGame.txt”));
TurnOverGame t = new TurnOverGame();
t.solution();
}
}
alexishuuuocn 