Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
3.0 kB
3
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

Code:
package TurnOverGame;

import java.io.FileInputStream;
import java.util.Scanner;

public class turnOverGame {
	static int [][] arr;
	static int m;
	static int min;
	static 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);
		}
	}
	static int [] dx = {-1, 0, 1, 0};
	static int [] dy = {0, 1, 0, -1};
	static void lat(int x, int y) {
		arr[x][y] = 1 - arr[x][y];
		for (int i = 0; i < 4; i++) {
			int x1 = x + dx[i];
			int y1 = y + dy[i];
			if (x1 >= 0 && x1 < 4 && y1 >= 0 && y1 < 4) {
				arr[x1][y1] = 1 - arr[x1][y1];
			}
		}
		
	}
	static boolean 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;
	}
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("D://Trainee//SRV_training//src//TurnOverGame//turngame.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		sc.nextLine();
		for (int test_case = 1; test_case <= T; test_case++) {
			System.out.println("Case #" + test_case);
			arr = new int [4][4];
			for (int i = 0; i < 4; i++) {
				String s = sc.nextLine();
				for (int j = 0; j < 4; j++) {
					char c = s.charAt(j);
					if (c == 'b') arr[i][j] = 0;
					else if (c == 'w') arr[i][j] = 1;
				}
			}
			m = 10000;
			Try (0,0,0);
			if (m == 10000) System.out.println("impossible");
			else System.out.println(m);
		}
	}
}