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