Untitled

 avatar
unknown
plain_text
2 years ago
1.5 kB
7
Indexable
import java.util.Scanner;

public class Solution {

	static Scanner scanner=new Scanner(System.in);
	static int res,dir[][]={{-1,0},{1,0},{0,1},{0,-1}};
	
	static boolean check(int[][] a){
		int f=a[0][0];
		for(int i=0;i<4;++i) for(int j=0;j<4;++j) if(a[i][j]!=f) return false;
		return true;
	}
	
	static void bt(int[][] a,int k,int cnt){
		if(cnt>=res)
			return;
		
		if(check(a))
			res=Math.min(res,cnt);
		
		if(k==16)
			return;
		
		int x=k/4, y=k%4;
		
		for(int i=0;i<2;++i) if(i==0) {
			bt(a,k+1,cnt);
		}else{
			a[x][y]=a[x][y]==1?0:1;
			for(int opt=0;opt<4;++opt){
				int nx=x+dir[opt][0],ny=y+dir[opt][1];
				if(nx>=0 && nx<4 && ny>=0 && ny<4)
					a[nx][ny]=a[nx][ny]==1?0:1;
			}
			
			bt(a,k+1,cnt+1);
			
			for(int opt=0;opt<4;++opt){
				int nx=x+dir[opt][0],ny=y+dir[opt][1];
				if(nx>=0 && nx<4 && ny>=0 && ny<4)
					a[nx][ny]=a[nx][ny]==1?0:1;
			}
			a[x][y]=a[x][y]==1?0:1;
		}
	}
	
	static void exec(int test){
		int[][] a=new int[4][4];
		for(int i=0;i<4;++i) {
			char[] tmp=scanner.next().toCharArray();
			for(int j=0;j<4;++j){
				a[i][j]=tmp[j]=='b'?1:0;
			}
		}
		
		res=Integer.MAX_VALUE;
		bt(a,0,0);
		
		if(res==Integer.MAX_VALUE)
			System.out.printf("Case #%d\nimpossible\n",test);
		else
			System.out.printf("Case #%d\n%d\n",test,res);
	}
	
	public static void main(String[] args) {
		int t=Integer.parseInt(scanner.next());
		
		for(int test=1;test<=t;++test)
			exec(test);
		
		scanner.close();
	}
}
Editor is loading...