Minimal Coin Path on a Colored Chessboard

You are given an m × m chessboard. Each cell of the board is either colored red, colored yellow, or has no color. You need to travel from the top‐left cell (cell (1,1)) to the bottom‐right cell (cell (m,m)).

At any moment, the cell you are on must be colored. You can only move in the four cardinal directions (up, down, left, or right). When moving from one cell to another:

• If the two cells have the same color, no coin is spent.
• If they have different colors, you spend 1 coin.

In addition, you are allowed to cast a spell by spending 2 coins that temporarily colors an adjacent cell that is originally uncolored. When you cast the spell you can choose either red or yellow for that cell. However, the spell cannot be cast in consecutive moves. In other words, if you use the spell to temporarily color a cell and step onto it, you cannot cast a spell in your next move. You can resume casting the spell once you step from a temporarily colored cell onto a normally colored cell. Note that once you leave a temporarily colored cell, it reverts to being uncolored immediately.

Your task is to determine the minimum number of coins needed to reach the bottom‐right cell from the top‐left cell.

Note: The chessboard input is provided such that the starting cell (top‐left) is always colored. The destination cell (bottom‐right) is also originally colored.

All formulas are given in \(\LaTeX\) format. For example, the cost for moving with a color change is given by \(1\) coin and the magic cost is \(2\) coins.

inputFormat

The first line contains a single integer m (\(1 \le m \le 1000\)), representing the size of the chessboard.

Each of the next m lines contains m tokens separated by spaces. Each token is one of the following:

• R — a naturally red cell
• Y — a naturally yellow cell
• N — a blank cell (no color)

The top-left cell is guaranteed to be either R or Y, and the bottom-right cell is also originally colored (R or Y).

outputFormat

Output a single integer, the minimum number of coins required to travel from the top-left cell to the bottom-right cell under the rules described above.

sample

2
R N
N Y

3