/ 
実行時間制限: 2.5 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
N 行 N 列のマス目があり、上から i (1 \leq i \leq N) 行目・左から j 列目 (1 \leq j \leq N) のマスを (i, j) と表します。
各マスは最初赤色か青色で塗られており、マス (i, j) は c_{i,j}=R のとき赤色で、c_{i,j}=B のとき青色で塗られています。
あなたは、いくつかのマスの色を紫色に変えることで、以下の 2 つの条件を同時に満たすようにしたいです。
条件1 赤色と紫色のマスのみを通って、マス (1, 1) からマス (N, N) に移動できる。
条件2 青色と紫色のマスのみを通って、マス (1, N) からマス (N, 1) に移動できる。
ただし、移動できるとは、該当する色のマスのみを通って上下左右に隣接するマスへの移動を繰り返すことで、 出発地点から到着地点までたどり着けることを指します。
条件を満たすには、最小で何個のマスを紫色に変えなければならないでしょうか。
制約
- 3 \leq N \leq 500
- c_{i,j} は
RまたはB - c_{1,1} および c_{N,N} は
R - c_{1,N} および c_{N,1} は
B - N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
c_{1,1}c_{1,2}\cdotsc_{1,N}
c_{2,1}c_{2,2}\cdotsc_{2,N}
\vdots
c_{N,1}c_{N,2}\cdotsc_{N,N}
出力
答えを出力してください。
入力例 1
5 RBRBB RBRRR RRRBR RBBRB BBRBR
出力例 1
3
以下の図のように、マス (1, 3), (3, 2), (4, 5) の 3 個を紫色に変えると、条件を満たすようになります。
入力例 2
5 RBBBB BBBBB BBBBB BBBBB BBBBR
出力例 2
7
以下の図のように、マス (1, 2), (2, 2), (2, 3), (3, 3), (3, 4), (4, 4), (4, 5) の 7 個を紫色に変えると、条件を満たすようになります。
入力例 3
10 RRBBBBBBBB BRRBBBBBBB BBRRBBBBBB BBBRRBBBBB BBBBRRBBBB BBBBBRRBBB BBBBBBRRBB BBBBBBBRRB BBBBBBBBRR BBBBBBBBBR
出力例 3
2
入力例 4
17 RBBRRBRRRRRBBBBBB BBRBRBRRBRRBRRBBR BRBRBBBRBBRBBRBBB RBRRBBBBBBRRBRRRR RRRRRBRBRRRBBRBBR RRRRRBRRBRBBRRRBB BBBRRRBRBRBBRRRBB BBRRRBRBBBRBRRRBR RRBBBBBBBBBBBRBRR RRRBRRBRBRBRBRBBB RRBRRRRBRBRRBRBBR RRRBBRBRBBBRBBRBR BBRBBRRBRRRBBRBBB BBBRBRRRRRRRBBRBB RRRRRBRBRBBRRBRRR BRRRRBBBRRRBRRBBB BBRRBBRRRBBBRBBBR
出力例 4
8
Score: 500 points
Problem Statement
There is a grid with N rows and N columns. Let (i, j) (1 \leq i \leq N, 1 \leq j \leq N) denote the cell at the i-th row from the top and the j-th column from the left. Each cell is initially painted red or blue, with cell (i, j) being red if c_{i,j}=R and blue if c_{i,j}=B. You want to change the colors of some cells to purple so that the following two conditions are simultaneously satisfied:
Condition 1: You can move from cell (1, 1) to cell (N, N) by only passing through cells that are red or purple.
Condition 2: You can move from cell (1, N) to cell (N, 1) by only passing through cells that are blue or purple.
Here, "You can move" means that you can reach the destination from the starting point by repeatedly moving to a horizontally or vertically adjacent cell of the relevant colors.
What is the minimum number of cells that must be changed to purple to satisfy these conditions?
Constraints
- 3 \leq N \leq 500
- Each c_{i,j} is
RorB. - c_{1,1} and c_{N,N} are
R. - c_{1,N} and c_{N,1} are
B. - N is an integer.
Input
The input is given from Standard Input in the following format:
N
c_{1,1}c_{1,2}\cdotsc_{1,N}
c_{2,1}c_{2,2}\cdotsc_{2,N}
\vdots
c_{N,1}c_{N,2}\cdotsc_{N,N}
Output
Print the answer.
Sample Input 1
5 RBRBB RBRRR RRRBR RBBRB BBRBR
Sample Output 1
3
As shown in the figure below, changing cells (1, 3), (3, 2), (4, 5) to purple satisfies the conditions.
Sample Input 2
5 RBBBB BBBBB BBBBB BBBBB BBBBR
Sample Output 2
7
As shown in the figure below, changing cells (1, 2), (2, 2), (2, 3), (3, 3), (3, 4), (4, 4), (4, 5) to purple satisfies the conditions.
Sample Input 3
10 RRBBBBBBBB BRRBBBBBBB BBRRBBBBBB BBBRRBBBBB BBBBRRBBBB BBBBBRRBBB BBBBBBRRBB BBBBBBBRRB BBBBBBBBRR BBBBBBBBBR
Sample Output 3
2
Sample Input 4
17 RBBRRBRRRRRBBBBBB BBRBRBRRBRRBRRBBR BRBRBBBRBBRBBRBBB RBRRBBBBBBRRBRRRR RRRRRBRBRRRBBRBBR RRRRRBRRBRBBRRRBB BBBRRRBRBRBBRRRBB BBRRRBRBBBRBRRRBR RRBBBBBBBBBBBRBRR RRRBRRBRBRBRBRBBB RRBRRRRBRBRRBRBBR RRRBBRBRBBBRBBRBR BBRBBRRBRRRBBRBBB BBBRBRRRRRRRBBRBB RRRRRBRBRBBRRBRRR BRRRRBBBRRRBRRBBB BBRRBBRRRBBBRBBBR
Sample Output 4
8