Untitled
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...