题目描述

强哥是一名城市规划师，他正在设计一个 $N$ 行 $N$ 列的城市交通网络（用 $(i, j)$ 表示网络第 $i$ 行第 $j$ 列的节点）。城市中有两种类型的道路：红色道路代表公交专用道，蓝色道路代表自行车专用道。

现在强哥需要在一些节点建设紫色道路（紫色道路既可以作为公交专用道使用，也可以作为自行车专用道使用），使得城市交通网络同时满足以下两个出行需求：

• 从居民区 $(1, 1)$ 到市中心 $(N, N)$，保证存在一条路径，使得公交车辆可以只经过红色道路和紫色道路；
• 从公园 $(1, N)$ 到体育场 $(N, 1)$，保证存在一条路径，使得自行车可以只经过蓝色道路和紫色道路。

注意，车辆和自行车可以在相邻节点间往任何一个方向行驶（上下左右）。

那么，强哥至少需要建设多少条紫色道路，才能同时满足以上两个出行需求呢？

输入格式

输入共 $N+1$ 行。

第一行，读入 $N$；

接下来 $N$ 行，读入这个交通网络图。其中以 R 代表红色道路（公交专用道），以 B 代表蓝色道路（自行车专用道）。

输出格式

输出仅一行，为最少需要建设的紫色道路数量。

【约定】

• $3\ \leq\ N\ \leq\ 500$；
• 保证任意一个节点一定是 R 或 B 中的一个；
• 保证 $(1, 1)$ 和 $(N, N)$ 为红色道路；
• 保证 $(1, N)$ 和 $(N, 1)$ 为蓝色道路；
• 保证 $N$ 是一个整数。

输入输出样例 #1

输入 #1

5
RBRBB
RBRRR
RRRBR
RBBRB
BBRBR

输出 #1

3

输入输出样例 #2

输入 #2

5
RBBBB
BBBBB
BBBBB
BBBBB
BBBBR

输出 #2

7

输入输出样例 #3

输入 #3

10
RRBBBBBBBB
BRRBBBBBBB
BBRRBBBBBB
BBBRRBBBBB
BBBBRRBBBB
BBBBBRRBBB
BBBBBBRRBB
BBBBBBBRRB
BBBBBBBBRR
BBBBBBBBBR

输出 #3

2

输入输出样例 #4

输入 #4

17
RBBRRBRRRRRBBBBBB
BBRBRBRRBRRBRRBBR
BRBRBBBRBBRBBRBBB
RBRRBBBBBBRRBRRRR
RRRRRBRBRRRBBRBBR
RRRRRBRRBRBBRRRBB
BBBRRRBRBRBBRRRBB
BBRRRBRBBBRBRRRBR
RRBBBBBBBBBBBRBRR
RRRBRRBRBRBRBRBBB
RRBRRRRBRBRRBRBBR
RRRBBRBRBBBRBBRBR
BBRBBRRBRRRBBRBBB
BBBRBRRRRRRRBBRBB
RRRRRBRBRBBRRBRRR
BRRRRBBBRRRBRRBBB
BBRRBBRRRBBBRBBBR

输出 #4

8