Score: $500$ points

问题陈述

有一个 $N$ 行 $N$ 列的网格。设 $(i, j)$ $(1 \leq i \leq N, 1 \leq j \leq N)$ 表示从顶部数第 $i$ 行，从左边数第 $j$ 行的单元格。每个单元格最初被涂成红色或蓝色，如果 $c_{i,j}=$R 则单元格 $(i, j)$ 是红色的，如果 $c_{i,j}=$B 则单元格是蓝色的。你想要将一些单元格的颜色改为紫色，以便同时满足以下两个条件：

条件 1：你可以通过只经过红色或紫色的单元格，从单元格 $(1, 1)$ 移动到单元格 $(N, N)$。 条件 2：你可以通过只经过蓝色或紫色的单元格，从单元格 $(1, N)$ 移动到单元格 $(N, 1)$。

在这里，“你可以移动”意味着你可以通过重复移动到目标单元格的水平或垂直相邻单元格来到达目的地，这些单元格具有相关的颜色。

为了满足这些条件，必须将最少多少个单元格改为紫色？

以上为大语言模型 kimi 翻译，仅供参考。

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 R or B.
• $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}$$\cdots$$c_{1,N}$

$c_{2,1}$$c_{2,2}$$\cdots$$c_{2,N}$

$\vdots$

$c_{N,1}$$c_{N,2}$$\cdots$$c_{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