TopCoder problem "CornersGame" used in SRM 308 (Division I Level Two)

Problem Statement


This problem contains an image that can be viewed in the applet.

A player has four draughts which are placed in the bottom right corner of a 6 x 6 chessboard. The draughts are arranged in a square with 2 rows and 2 columns (see picture below). Some cells on the board may contain red flags, and some may contain stones.

The player's goal is to move all the draughts to the top left corner and arrange them in a square using a minimal number of moves. The draughts are indistinguishable, so their order in the final position doesn't matter. The target cells are guaranteed to be free. There are two kinds of moves that can be made by a draught. The first is to move to any vertically or horizontally adjacent free cell. The second is to jump over a single vertically or horizontally adjacent draught or stone into a free cell. The player can never move a draught into a cell that contains a flag, stone or other draught and he can never jump over a flag or an empty space.

You will be given a String[] board where each element represents a single row of the chessboard. The rows are given from top to bottom, and each row is given from left to right. '.' represents a free cell, 'r' represents a cell with a red flag, and 's' represents a cell with a stone. Return the minimal number of moves necessary to reach the goal, or -1 if it is impossible.



Method signature:int countMoves(String[] board)
(be sure your method is public)


-board will contain exactly 6 elements.
-Each element of board will contain exactly 6 characters.
-Each element of board will contain only the characters 'r', 's', and '.'.
-board will contain '.' characters at the initial and desired final positions of the draughts.


Returns: 16
Returns: 19
The board shown on the picture above.
Returns: -1
We can not make any move.
Returns: 54

Problem url:

Problem stats url:




PabloGilberto , brett1479 , vorthys , Olexiy

Problem categories:

Graph Theory