Untitled

 avatar
unknown
plain_text
2 years ago
1.7 kB
4
Indexable
package turnovergame;

import java.util.Scanner;

public class test {
static char[][] matrix=new char[4][4];
static int ans=0;
static int dx[] = {-1,0,1,0};
static int dy[] = {0,-1,0,1};
static boolean checkWhite(){
	for(int j=0;j<4;j++){	
		for(int k=0;k<4;k++){
			if(matrix[j][k]=='b')
				return false;
		}
	}
	return true;
}
static boolean checkBlack(){
	for(int j=0;j<4;j++){	
		for(int k=0;k<4;k++){
			if(matrix[j][k]=='w')
				return false;
		}
	}
	return true;
}
static void LatCo(int x,int y){
	if(matrix[x][y]=='b')
		matrix[x][y]='w';
	else {
		matrix[x][y]='b';
	}
	for(int j=0;j<4;j++){
		int r=x+dx[j];
		int c=y+dy[j];
		
		if(r>=0 && r<4 && c>=0 && c<4 && matrix[r][c]=='b'){
			matrix[r][c]='w';}
		else if(r>=0 && r<4 && c>=0 && c<4 && matrix[r][c]=='w'){
			matrix[r][c]='b';
		}
	}
}
static void Backtrack(int k,int step){
	if(checkBlack() || checkWhite()){
		if(step<ans){
			ans=step;
		}
		return;
	}
	if(k==16){
		return;
	}
	int x=k/4;
	int y=k%4;
	for(int i=0;i<2;i++){
		if(i==0){
			Backtrack(k+1,step);
		}
		else {
			LatCo(x, y);
			Backtrack(k+1, step+1);
			LatCo(x, y);
		}
	}
}
public static void main(String[] args) {
	Scanner scanner=new Scanner(System.in);
	int tc=scanner.nextInt();
	scanner.nextLine();
	for(int i=0;i<tc;i++){
		for(int j=0;j<4;j++){
			String S=scanner.nextLine();
			for(int k=0;k<4;k++){
				matrix[j][k]=S.charAt(k);
			}
		}
		ans=16;
		Backtrack(0, 0);
		if(ans==16){
			System.out.println("Case #"+(i+1));
			System.out.println("impossible");
		}
		else {
			System.out.println("Case #"+(i+1));
			System.out.println(ans);
		}
	}
}
}

Editor is loading...