The Java Program: A_block/blockYiu.java

  1 /*
  2 ACM ICPC Southeast Regional Contest 2009
  3 
  4 Block Game
  5 
  6 Author: Yiu Yu Ho
  7 */
  8 
  9 import java.io.*;
 10 import java.util.*;
 11 
 12 public class blockYiu
 13 {
 14         public Scanner in = new Scanner(System.in);
 15         public PrintStream out = System.out;
 16 
 17         public int oo = 987654321;
 18 
 19         public Map<String, Integer> cost;
 20         
 21         public void main()
 22         {
 23                 int i, j, k, x, y, z;
 24                 int C, len;
 25                 String now, code;
 26                 String special;
 27                 char[][] g;
 28                 boolean[] used;
 29                 char A;
 30                 int res;
 31 
 32                 special = in.next();
 33                 while(!"*".equals(special))
 34                 {
 35                         //read input grid
 36                         g = new char[6][];
 37                         for(i=0;i<6;++i) g[i] = in.next().toCharArray();
 38                         
 39                         //Queue for BFS (Breadth First Search)
 40                         Queue<String> Q = new LinkedList<String>();
 41                         //cost mapping from board state to number of moves applied
 42                         cost = new HashMap<String, Integer>();
 43                         
 44                         res = oo;
 45                         
 46                         //initial state cost = 0
 47                         code = cat(g);
 48                         cost.put(code, 0);
 49                         Q.offer(code);
 50 
 51 BFS:
 52                         while(!Q.isEmpty())
 53                         {
 54                                 //get item from queue
 55                                 now = Q.poll();
 56                                 C = cost.get(now);
 57                                 
 58                                 //g = state in grid form
 59                                 g = parse(now);
 60                                 used = new boolean[26];
 61                                 
 62                                 //visit g/now's neighbors
 63                                 for(i=0;i<6;++i)
 64                                 for(j=0;j<6;++j) if(g[i][j] != '.')
 65                                 {
 66                                         A = g[i][j];
 67                                         
 68                                         //move each piece once, when it is first encountered in a row major order scan.
 69                                         //Thus, (i, j) is the left most cell of a horizontal piece or a top most cell 
 70                                         //of a vertical piece.
 71                                         if(used[A - 'A']) continue;
 72                                         used[A - 'A'] = true;
 73                                         
 74                                         //If this is the special piece, then answer is 1 step away, assume to the right
 75                                         //of the piece is clear (all '.')
 76                                         //Since we are using BFS with uniform cost (moving from state to state all cost 1),
 77                                         //this is optimal
 78                                         if(special.charAt(0) == A && clear(g, i, j+2))
 79                                         {
 80                                                 res = C+1;
 81                                                 break BFS;
 82                                         }
 83 
 84                                         if(j+1<6 && A == g[i][j+1])
 85                                         {
 86                                                 //horizontal piece, len is the length of this piece (number of cells it has)
 87                                                 len = (j+2 < 6 && A == g[i][j+2] ? 3 : 2);
 88                                                 
 89                                                 //moving to the right, so long as nothing in the way
 90                                                 for(k=j+1;k+len-1<6 && g[i][k+len-1]=='.';++k)
 91                                                 {
 92                                                         //moving by erasing the first cell on the left 
 93                                                         //and adding 1 more cell to the right
 94                                                         g[i][k-1] = '.';
 95                                                         g[i][k+len-1] = A;
 96                                                         
 97                                                         //calculate new state as a String, and check for cost (which is equivalent to 
 98                                                         //checking if the state visited or not in BFS)
 99                                                         code = cat(g);
100                                                         if(!cost.containsKey(code))
101                                                         {
102                                                                 //Add to the queue if this is a new state
103                                                                 cost.put(code, C+1);
104                                                                 Q.offer(code);
105                                                         }
106                                                 }
107                                                 
108                                                 //restore back to original board (now)
109                                                 for(k=k+len-2;k>=0 && g[i][k]==A;--k) g[i][k] = '.';
110                                                 for(z=0;z<len;++z) g[i][j+z] = A;
111                                                 
112                                                 //try moving left, so long as nothing is in the way
113                                                 for(k=j-1;k>=0 && g[i][k]=='.';--k)
114                                                 {
115                                                         //same idea as above, except erasing right most piece and add to the left
116                                                         g[i][k+len] = '.';
117                                                         g[i][k] = A;
118                                                         
119                                                         //check visited (same as above)
120                                                         code = cat(g);
121                                                         if(!cost.containsKey(code))
122                                                         {
123                                                                 cost.put(code, C+1);
124                                                                 Q.offer(code);
125                                                         }
126                                                 }
127                                                 
128                                                 //restore, this is necessary because we will use the same 
129                                                 //board, g, for moving the other pieces
130                                                 for(++k;k<6 && g[i][k]==A;++k) g[i][k] = '.';
131                                                 for(z=0;z<len;++z) g[i][j+z] = A;
132                                         }
133                                         else
134                                         {
135                                                 //vertical piece, everything is done analogously to the horizontal case
136                                                 len = (i+2 < 6 && A == g[i+2][j] ? 3 : 2);
137                                                 
138                                                 for(k=i+1;k+len-1<6 && g[k+len-1][j]=='.';++k)
139                                                 {
140                                                         g[k-1][j] = '.';
141                                                         g[k+len-1][j] = A;
142 
143                                                         code = cat(g);
144                                                         if(!cost.containsKey(code))
145                                                         {
146                                                                 cost.put(code, C+1);
147                                                                 Q.offer(code);
148                                                         }
149                                                 }
150                                                 
151                                                 //restore
152                                                 for(k=k+len-2;k>=0 && g[k][j]==A;--k) g[k][j] = '.';
153                                                 for(z=0;z<len;++z) g[i+z][j] = A;
154 
155                                                 for(k=i-1;k>=0 && g[k][j]=='.';--k)
156                                                 {
157                                                         g[k+len][j] = '.';
158                                                         g[k][j] = A;
159 
160                                                         code = cat(g);
161                                                         if(!cost.containsKey(code))
162                                                         {
163                                                                 cost.put(code, C+1);
164                                                                 Q.offer(code);
165                                                         }
166                                                 }
167 
168                                                 //restore
169                                                 for(++k;k<6 && g[k][j]==A;++k) g[k][j] = '.';
170                                                 for(z=0;z<len;++z) g[i+z][j] = A;
171                                         }
172                                 }
173                         }
174                         
175                         out.println(res < oo ? res : -1);
176                         special = in.next();
177                 }
178         }
179         
180         //make sure g[i][j..5] are all '.'s
181         //This is used to check for a clearing path of the special piece (to move it out)
182         public boolean clear(char[][] g, int i, int j)
183         {
184                 while(j < 6)
185                 {
186                         if(g[i][j] != '.') return false;
187                         ++j;
188                 }
189                 return true;
190         }
191         
192         //convert a char[][] board into a String for state storage (taking advantage of java String hashing) 
193         public String cat(char[][] g)
194         {
195                 StringBuffer ret = new StringBuffer("");
196                 for(int i=0;i<g.length;++i) ret.append(new String(g[i]));
197                 return ret.toString();
198         }
199         
200         //convert a String state back to a char[][] board
201         public char[][] parse(String s)
202         {
203                 char[][] r = new char[6][];
204                 for(int i=0;i<6;++i) r[i] = s.substring(i*6, (i+1)*6).toCharArray();
205                 return r;
206         }
207 
208         public static void main(String[] args)
209         {
210                 long startTime = System.currentTimeMillis();
211                 (new blockYiu()).main();
212                 long endTime = System.currentTimeMillis();
213 
214                 System.err.println("Time = " + (endTime - startTime) + "(ms)");
215         }
216 }