Aizu Online Judge 0131 Doctor's Strange Particles

■0131 Doctor's Strange Particles

いわゆるライツアウト．最上段の反転パターン方法を固定すると，あとは自動的に決定するので，最上段の反転パターンのみを全探索．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int[][] a, b;  
17.  int[][] tmp;  
18.  int n;  
19.   
20.  void run(){  
21.   n=10;  
22.   for(int m=sc.nextInt(); m>0; m--){  
23.    a=new int[n][n];  
24.    for(int j=0; j<n; j++){  
25.     for(int i=0; i<n; i++){  
26.      a[j][i]=sc.nextInt();  
27.     }  
28.    }  
29.    solve();  
30.   }  
31.  }  
32.   
33.  void solve(){  
34.   tmp=new int[n][n];  
35.   b=new int[n][n];  
36.   for(int sup=0; sup<1<<n; sup++){  
37.    for(int j=0; j<n; j++){  
38.     System.arraycopy(a[j], 0, tmp[j], 0, n);  
39.     Arrays.fill(b[j], 0);  
40.    }  
41.    for(int i=0; i<n; i++){  
42.     if(((sup>>i)&1)!=0){  
43.      reverse(i, 0);  
44.     }  
45.    }  
46.    for(int j=1; j<n; j++){  
47.     for(int i=0; i<n; i++){  
48.      if(tmp[j-1][i]==1){  
49.       reverse(i, j);  
50.      }  
51.     }  
52.    }  
53.    int c=0;  
54.    for(int i=0;i<n;i++){  
55.     c+=tmp[n-1][i];  
56.    }  
57.    if(c==0){  
58.     for(int j=0;j<n;j++){  
59.      for(int i=0;i<n;i++){  
60.       print(b[j][i]+(i==n-1?"\n":" "));  
61.      }  
62.     }  
63.     return;  
64.    }  
65.   }  
66.  }  
67.   
68.  void reverse(int x, int y){  
69.   int[] dx={0, 0, 0, -1, 1};  
70.   int[] dy={0, -1, 1, 0, 0};  
71.   for(int i=0; i<5; i++){  
72.    int x2=x+dx[i];  
73.    int y2=y+dy[i];  
74.    if(x2>=0&&x2<n&&y2>=0&&y2<n){  
75.     tmp[y2][x2]=1-tmp[y2][x2];  
76.    }  
77.   }  
78.   b[y][x]=1-b[y][x];  
79.  }  
80.   
81.  void debug(Object... os){  
82.   System.err.println(Arrays.deepToString(os));  
83.  }  
84.   
85.  void print(String s){  
86.   System.out.print(s);  
87.  }  
88.   
89.  void println(String s){  
90.   System.out.println(s);  
91.  }  
92.   
93.  public static void main(String[] args){  
94.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
95.   new Main().run();  
96.  }  
97. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int[][] a, b;
 int[][] tmp;
 int n;

 void run(){
  n=10;
  for(int m=sc.nextInt(); m>0; m--){
   a=new int[n][n];
   for(int j=0; j<n; j++){
    for(int i=0; i<n; i++){
     a[j][i]=sc.nextInt();
    }
   }
   solve();
  }
 }

 void solve(){
  tmp=new int[n][n];
  b=new int[n][n];
  for(int sup=0; sup<1<<n; sup++){
   for(int j=0; j<n; j++){
    System.arraycopy(a[j], 0, tmp[j], 0, n);
    Arrays.fill(b[j], 0);
   }
   for(int i=0; i<n; i++){
    if(((sup>>i)&1)!=0){
     reverse(i, 0);
    }
   }
   for(int j=1; j<n; j++){
    for(int i=0; i<n; i++){
     if(tmp[j-1][i]==1){
      reverse(i, j);
     }
    }
   }
   int c=0;
   for(int i=0;i<n;i++){
    c+=tmp[n-1][i];
   }
   if(c==0){
    for(int j=0;j<n;j++){
     for(int i=0;i<n;i++){
      print(b[j][i]+(i==n-1?"\n":" "));
     }
    }
    return;
   }
  }
 }

 void reverse(int x, int y){
  int[] dx={0, 0, 0, -1, 1};
  int[] dy={0, -1, 1, 0, 0};
  for(int i=0; i<5; i++){
   int x2=x+dx[i];
   int y2=y+dy[i];
   if(x2>=0&&x2<n&&y2>=0&&y2<n){
    tmp[y2][x2]=1-tmp[y2][x2];
   }
  }
  b[y][x]=1-b[y][x];
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}