分数: 500 点
问题陈述
有一个网格 N 行和 N 列。让 (i, j) (1 \leq i \leq N, 1 \leq j \leq N) 表示位于 i从顶部算起的第行和 j左起第 列。每个单元格最初被涂成红色或蓝色,并且单元格 (i, j) 为红色,如果 c_{i,j}=R 和蓝色如果 c_{i,j}=B。您想要将某些单元格的颜色更改为紫色,以便同时满足以下两个条件:
条件 1:您可以从单元格中移动 (1, 1) 到单元格 (N, N) 仅通过红色或紫色的细胞。
条件 2:您可以从单元格中移动 (1, N) 到单元格 (N, 1) 仅通过蓝色或紫色的单元格。
这里,“你可以移动”表示从起点重复移动到相关颜色的水平或垂直相邻的单元格即可到达目的地。
满足这些条件必须更改为紫色的最小单元格数量是多少?
约束
- 3 \leq N \leq 500
- 每个 c_{i,j} is
RorB. - 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) 为紫色满足条件。

示例输入 2
5 RBBBB BBBBB BBBBB BBBBB BBBBR
示例输出 2
7
如下图所示,更改单元格 (1, 2), (2, 2), (2, 3), (3, 3), (3, 4), (4, 4), (4, 5) 为紫色满足条件。

示例输入 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