# Untitled

unknown
plain_text
a year ago
1.5 kB
3
Indexable
Never
```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();
}
}
```