FlipFlop

Flip-Flop is a puzzle played with a m by n grid of cells. Each cell has a colored peg, which can be one of three colors: Red, Green, or Blue. Here are some examples of what the grid may look like ('R' for Red, 'G' for Green, 'B' for Blue):

• RRGGB      RGBRGB      RRR
  RRRGG      GBRGBR      GGG
  GRRRR      BRGBRG      BBB
  GGRRR                  
  BGGRR                  
  

A color-switch is defined as changing the peg from one color to another. Red switches to Green. Green switches to Blue. Blue switches to Red.

A move is made by first choosing one of the pegs and doing a color-switch on it (the flip). Then, its (up to) four neighboring pegs are color-switched (the flop). Diagonal neighbors do not count, only vertical and horizontal neighbors do. Edges do not wrap around.

For example (the coordinates are represented as a (row, col) pair):

  12345         12345         12345
1 BBBGG       1 BBBBB       1 BBBBB
2 BBBBG       2 BBBBB       2 BBBBB
3 BBBBB  -->  3 BBBBB  -->  3 BBBBB
4 GBBBB       4 GBBBB       4 BBBBB
5 GGBBB       5 GGBBB       5 BBBBB

Move 1     |  Move 2
-----------+------------
flip(1,5)  |  flip(5,1)
flop(1,4)  |  flop(4,1)
flop(2,5)  |  flop(5,2)

Another example:

  12345         12345         12345         12345         12345
1 BRBBG       1 BGBBG       1 BBBBG       1 BBBBG       1 BBBBB
2 RRRGG       2 GGGGG       2 BBBGG       2 BBBGG       2 BBBBB
3 BRGBG  -->  3 BGGBG  -->  3 BBGBG  -->  3 BBBBG  -->  3 BBBBB
4 BGGGB       4 BGGGB       4 BGGGB       4 BBBBB       4 BBBBB
5 BBGBB       5 BBGBB       5 BBGBB       5 BBBBB       5 BBBBB
6 BBBBB       6 BBBBB       6 BBBBB       6 BBBBB       6 BBBBB

Move 1     |  Move 2     |  Move 3     |  Move 4
-----------+-------------+-------------+------------
flip(2,2)  |  flip(2,2)  |  flip(4,3)  |  flip(2,5)
flop(1,2)  |  flop(1,2)  |  flop(3,3)  |  flop(1,5)
flop(2,1)  |  flop(2,1)  |  flop(4,2)  |  flop(2,4)
flop(2,3)  |  flop(2,3)  |  flop(4,4)  |  flop(3,5)
flop(3,2)  |  flop(3,2)  |  flop(5,3)  |

The object of Flip-Flop is to start with some initial board position and reach the board with all Blue pegs by making a series of moves. Some initial positions are solvable. But for others, it is impossible. For each solvable initial position, there exists a minimum number of moves required to solve the puzzle.

You are given a String[], board, as the initial board position. Each element of board represents a row of the initial position by the colors of the pegs, with Element 0 as the first row, Element 1 as the second row, and so on. Your task is to write a function that returns the minimum number of moves to solve the puzzle. If the given initial position is unsolvable, return -1.