← 返回题目列表

AtCoder · arc177_c

C. 路由

中文机器翻译题面 查看原题

分数: 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 R or 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) 为紫色满足条件。


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