Block Puzzle

Block Puzzle is played on a square grid divided into unit squares. Some cells are marked as start cells, and exactly one cell is marked as the goal cell.

The game begins by standing a $1 \times 1 \times 2$ block on one of the start cells, so that a $1 \times 1$ face touches that cell. The goal is to roll the block until it stands on the goal cell, meaning a $1 \times 1$ face touches the goal cell.

The block moves by rolling. When a $1 \times 1$ face touches the grid, you can roll the block in all four directions. When a $2 \times 1$ face touches the grid, you can only roll it so that a $1 \times 1$ face ends up touching the grid. In other words, you always roll the block about an edge of length 1.

The picture below shows every possible roll, with the state just before the roll drawn semi transparent.

The game is hard because some cells have holes in them. If the whole bottom face of the block sits over holes, the block falls into the hole and you lose. If the bottom face is $2 \times 1$ and only one of the two cells is a hole, the block does not fall. The block may also hang over the border of the board: when the bottom face is $2 \times 1$, one cell may be on the board and the other outside it.

Hongjun has played this game so much that he is bored with it. He wants to dig extra holes so that the game becomes unsolvable. Hongjun can turn any cell that is neither a start cell nor the goal cell into a hole.

Given the state of the board, write a program that finds the minimum number of cells Hongjun has to turn into holes to make the game unsolvable.

The first line contains the board size $N$ ($3 \le N \le 50$). Each of the next $N$ lines contains $N$ characters describing one row of the board.

'.' is an empty cell, 'H' is a hole, 'b' is a start cell, and '$' is the goal cell.

The board contains exactly one '$' and at least one 'b'.

Print the minimum number of cells that have to be turned into holes to make the game unsolvable. If the game cannot be made unsolvable, print -1.