1.4/clocks.java

   1 /*
   2 ID: raincro1
   3 LANG: JAVA
   4 TASK: clocks
   5 */
   6 import java.io.*;
   7 import java.util.*;
   8
   9 class clocks {
  10     static class IO {
  11         public BufferedReader   f;
  12         StringTokenizer         st;
  13         public PrintWriter      out;
  14
  15         public String           line;
  16
  17         public IO () throws IOException {
  18             f = new BufferedReader(new FileReader(name + ".in"));
  19             out = new PrintWriter(new BufferedWriter(new FileWriter(name + ".out")));
  20         }
  21
  22         public String nextLine() throws IOException {
  23             line = f.readLine();
  24             st = null;
  25             return line;
  26         }
  27
  28         public int nextIntLine() throws IOException {
  29             return Integer.parseInt(nextLine());
  30         }
  31
  32         public void tokenize() {
  33             st = new StringTokenizer(line);
  34         }
  35
  36         public String nextToken() {
  37             if(st == null) tokenize();
  38             return st.nextToken();
  39         }
  40
  41         public int nextIntToken() {
  42             return Integer.parseInt(nextToken());
  43         }
  44
  45         public void close() {
  46             out.close();                                  // close the output file
  47             System.exit(0);                               // don't omit this!
  48         }
  49     }
  50
  51     static boolean          debug = false;
  52     static String           name  = "clocks";
  53
  54     static IO               io;
  55
  56     //////////////////////////////////////////
  57
  58     static final byte[][]    moves = {
  59         { 0, 1, 3, 4 },
  60         { 0, 1, 2 },
  61         { 1, 2, 4, 5 },
  62         { 0, 3, 6 },
  63         { 1, 3, 4, 5, 7 },
  64         { 2, 5, 8 },
  65         { 3, 4, 6, 7 },
  66         { 6, 7, 8 },
  67         { 4, 5, 7, 8 }
  68     };
  69
  70     static State        state_pool = null;
  71
  72     static class Move {
  73         public  int      val;
  74         public  Move     pre;
  75
  76         public Move(Move pre, int val) {
  77             this.val = val;
  78             this.pre = pre;
  79         }
  80
  81         public void print() {
  82             if(pre == null) {
  83                 io.out.print(val + 1);
  84             }else{
  85                 pre.print();
  86                 io.out.printf(" %d", val + 1);
  87             }
  88         }
  89
  90         public void sys_print() {
  91             if(pre == null) {
  92                 System.out.print(val + 1);
  93             }else{
  94                 pre.sys_print();
  95                 System.out.printf(" %d", val + 1);
  96             }
  97         }
  98     }
  99
 100     static class State {
 101         public  Move    move;
 102         public  int     iter;           // move iteration
 103         public  int[]   state = null;
 104
 105         public  State   next = null;    // chain pointer
 106
 107         public State(Move move, int iter) {
 108             this.move = move;
 109             this.iter = iter;
 110         }
 111
 112         void check() {
 113             for(int i = 0; i < 9; i++){
 114                 if(state[i] != 0) return;
 115             }
 116
 117             move.print();
 118
 119             io.out.println();
 120             io.close();
 121         }
 122     }
 123
 124     static State genState(Move move, int mid, int iter, State first, State last) {
 125         State   st;
 126
 127         if(state_pool != null){
 128             st = state_pool;
 129             state_pool = st.next;
 130             st.next = null;
 131
 132             st.move = new Move(move, mid);
 133
 134             st.iter = iter;
 135
 136             for(int i = 0; i < 9; i++){
 137                 st.state[i] = first.state[i];
 138             }
 139         }else{
 140             st = new State(new Move(move, mid), iter);
 141             st.state = first.state.clone();
 142         }
 143
 144         // apply move
 145         for(int i = moves[mid].length - 1; i >= 0; i--){
 146             final int id = moves[mid][i];
 147             st.state[id] = (st.state[id] + 1) % 4;
 148         }
 149
 150         st.check();
 151
 152         last.next = st;     // don't forget to append the state
 153
 154         return st;
 155     }
 156
 157     static State poolState(State st){
 158         State n = st.next;
 159
 160         st.next = state_pool;
 161         state_pool = st;
 162
 163         return n;
 164     }
 165
 166     public static void main (String [] args) throws IOException {
 167         io = new IO();
 168
 169         State   first, last;
 170
 171         first = last = new State(null, 0);
 172
 173         first.state = new int [9];
 174
 175         for(int i = 0; i < 9; i++){
 176             if(i % 3 == 0) io.nextLine();
 177             first.state[i] = io.nextIntToken() / 3 % 4;
 178         }
 179
 180         first.check();
 181
 182         for(int id = 0; id < 9; id++){
 183             last = genState(null, id, 0, first, last);
 184         }
 185
 186         first = first.next;
 187
 188         for(int iii = 0; iii < 1000000; iii++){
 189             final Move  move = first.move;
 190             final int   mid = move.val;
 191             final int   iter = first.iter;
 192
 193             if(iter < 2){
 194                 last = genState(move, mid, iter + 1, first, last);
 195             }
 196
 197             for(int id = mid + 1; id < 9; id++){
 198                 last = genState(move, id, 0, first, last);
 199             }
 200
 201             first = poolState(first);
 202         }
 203
 204         // io.out.println(min_area);
 205         // io.close();
 206     }
 207 }
 208
 209