The Java Program: A_block/blockgame.java

  1 import java.io.*;
  2 import java.util.*;
  3 import java.awt.*;
  4 import java.text.*;
  5 import java.math.*;
  6 
  7 /**
  8  * Solution to Block Game. 
  9  * 
 10  * It's just a Breadth-First Search, keeping track of previously seen states.
 11  */
 12 class blockgame
 13 {
 14     public Scanner sc;
 15     public PrintStream ps;
 16 
 17     public String toString()
 18     {
 19         return "blockgame";
 20     }
 21     
 22     // The change in i and j for each of the four directions.
 23     // d=0 is up, d=1 is right, d=2 is down, d=3 is left.
 24     public static final int di[] = { -1, 0, 1, 0 };
 25     public static final int dj[] = { 0, 1, 0, -1 };
 26     
 27     // The (fixed) board size.
 28     public int n=6, m=6;
 29       
 30     /**
 31      * This is a State in the Breadth-First Search. 
 32      * A State consists of the current configuration of the board, and the move number.
 33      */
 34     public class State
 35     {
 36         // The board
 37         public char board[][];
 38         
 39         // The move number
 40         public int move;
 41         
 42         /**
 43          * Build a state.
 44          * 
 45          * @param b The Board
 46          * @param mm The Move Number
 47          */
 48         public State( char b[][], int mm )
 49         {
 50                 // Remember move number
 51                 move = mm;
 52                 
 53                 // Build a new board
 54                 board = new char[n][];
 55                 for( int i=0; i<b.length; i++ )
 56                 {
 57                         board[i] = Arrays.copyOf( b[i], b[i].length );
 58                 }
 59         }
 60         
 61         /**
 62          * Retrieve the Board from a State.
 63          * 
 64          * @return This State's Board
 65          */
 66         public char[][] getBoard()
 67         {
 68                 return board;
 69         }
 70         
 71         /**
 72          * Build a unique ID for this state.
 73          * This is going to be used to check for repeated states.
 74          * 
 75          * @return A unique ID for this state.
 76          */
 77         public String getID()
 78         {
 79                 StringBuffer buffer = new StringBuffer(100);
 80                 for( int i=0; i<board.length; i++ )
 81                 {
 82                     buffer.append( board[i] );  
 83                 }
 84                 
 85                 return buffer.toString();
 86         }
 87     }
 88     
 89     /**
 90      * Determine if (i,j) is on a board.
 91      * 
 92      * @param b A Board
 93      * @param i Row
 94      * @param j Column
 95      * @return true if Row i, Column j is on the board, otherwise false.
 96      */
 97     public boolean onboard( char b[][], int i, int j )
 98     {
 99         return i>=0 && j>=0 && i<b.length && j<b[i].length;
100     }
101     
102     /**
103      * Determine if the piece at (i,j) can move in direction d.
104      * 
105      * @param b A Board
106      * @param i Row
107      * @param j Column
108      * @param d Direction
109      * @return true if the if the piece at (i,j) can move in direction d, otherwise false.
110      */
111     public boolean canmove( char b[][], int i, int j, int d )
112     {
113         // 'up' is in direction d
114         int upi = i+di[d];
115         int upj = j+dj[d];
116         
117         // 'down' is in the direction opposite d
118         int dni = i-di[d];
119         int dnj = j-dj[d];
120         
121         // We can move if both 'up' and 'down' cells are on the board,
122         // if the 'up' cell is empty, and the 'down' cell belongs
123         // to the same piece as cell (i,j).
124         // Like this:
125         //
126         // .
127         // A
128         // A
129         return onboard( b, upi, upj ) && onboard( b, dni, dnj ) 
130             && b[upi][upj]=='.' && b[dni][dnj]==b[i][j]; 
131     }
132                 
133     /**
134      * This is the main method. 
135      * @throws Exception
136      */
137     public void doit() throws Exception
138     {
139         sc = new Scanner( System.in ); // new Scanner( new File( "blockgame.judge" ) );
140         ps = System.out; // new PrintStream( new FileOutputStream( "blockgame.solution" ) ); 
141         
142         for(;;)
143         {
144                 // Read in the char of the special piece, exit if it's '*'
145                 char ch = sc.next().charAt(0);
146                 if( ch=='*' ) break;
147                 
148                 // Read in the board
149                 char board[][] = new char[n][];
150                 for( int i=0; i<n; i++ )
151                 {
152                         board[i] = sc.next().toCharArray();
153                 }
154                 
155                 // Queue for BFS
156                 LinkedList<State> queue = new LinkedList<State>();
157                 
158                 // This will record states we've seen
159                 HashSet<String> seen = new HashSet<String>();
160                 
161                 // Put the first state on the queue, 
162                 // and say that we've seen it
163                 State state = new State( board, 0 );
164                 queue.add( state );
165                 seen.add( state.getID() );
166                 
167                 // This will hold the final answer
168                 int solution = -1;
169                 
170                 // Keep going until the queue is empty,
171                 // or until a solution is found
172                 while( queue.size()>0 && solution<0 )
173                 {
174                         // Get the state at the top of the queue,
175                         // and get its board
176                     state = queue.removeFirst();                        
177                         char b[][] = state.getBoard();
178                         
179                         // Look to see if the special piece has
180                         // been moved to the last row. If so, it can be
181                         // moved off, and the board is solved.
182                         for( int i=0; i<n; i++ )
183                         {
184                             if( b[i][m-1]==ch )
185                             {
186                                 solution = state.move;
187                                 break;
188                             }
189                         }
190                         
191                         // Go through the entire board, looking for pieces to move
192                         for( int i=0; i<b.length; i++ ) for( int j=0; j<b[i].length; j++ ) if( b[i][j]!='.')
193                         {
194                                 // Try all four directions
195                                 for( int d=0; d<4; d++ )
196                                 {
197                                         // If this piece can move in this direction...
198                                         if( canmove( b, i, j, d ) )
199                                         {
200                                                 // i,j is where the piece is now
201                                                 // ii, jj is where the piece will be as it moves
202                                                 int ii = i;
203                                                 int jj = j;
204                                                 
205                                                 // Make a copy of the board
206                                                 char newb[][] = new char[n][m];
207                                                 for( int k=0; k<n; k++ )
208                                                 {
209                                                         newb[k] = Arrays.copyOf( b[k], m );
210                                                 }
211                                                 
212                                                 // Check to see if its of size 2 or 3
213                                                 // (Actually, for 2, size=1, and for 3, size=2)
214                                                 int i3 = i-2*di[d];
215                                                 int j3 = j-2*dj[d];
216                                                 int size = onboard( newb, i3, j3 ) && newb[i3][j3]==newb[ii][jj] ? 2 : 1;
217                                                 
218                                                 // While the piece can still move...
219                                                 while( canmove( newb, ii, jj, d ) )
220                                                 {
221                                                         // Make the move
222                                                         newb[ii+di[d]][jj+dj[d]] = newb[ii][jj];
223                                                         newb[ii-size*di[d]][jj-size*dj[d]] = '.';
224                                                         
225                                                         // Build a new state
226                                                         State newstate = new State( newb, state.move+1 );
227                                                         String newid = newstate.getID();
228                                                         
229                                                         // If it hasn't been seen yet, add it to the queue
230                                                         // put it in the 'seen' set.
231                                                         if( !seen.contains( newid ) )
232                                                         {
233                                                                 queue.add( newstate );
234                                                                 seen.add( newid );
235                                                         }
236                                                         
237                                                         // Iterate, try again
238                                                         ii += di[d];
239                                                         jj += dj[d];
240                                                 }
241                                         }
242                                 }
243                         }                       
244                 }  
245                 
246                 // Now here's a special case: what about this input?
247                 //
248                 // A
249                 // ....AA
250                 // ......
251                 // ......
252                 // ......
253                 // ......
254                 // ......
255                 //
256                 // The algorithm will return 0 - it takes no moves to get the 
257                 // special piece to the edge of the board. But, it takes 1 move 
258                 // to get it OFF the board!
259                 ps.println( solution==0 ? 1 : solution );
260         }
261     }
262 
263         public static void main(String[] args) throws Exception
264         {
265                 long starttime = System.currentTimeMillis();
266                 new blockgame().doit();
267                 System.out.println( System.currentTimeMillis() - starttime );
268         }
269 }