CornersGame

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.