路线规划

时间限制：2.5s
空间限制：1024MB

题目描述

有一个 $N\times N$ 的网格，每个格子初始为红色 R 或蓝色 B。你可以把若干格子的颜色改成紫色，使以下两个条件同时成立：

1. 只经过红色或紫色格子，可以从 $(1,1)$ 走到 $(N,N)$；
2. 只经过蓝色或紫色格子，可以从 $(1,N)$ 走到 $(N,1)$。

每步只能走到上下左右相邻的格子。求最少需要改成紫色的格子数。

输入格式

N
c_{1,1}c_{1,2}...c_{1,N}
...
c_{N,1}c_{N,2}...c_{N,N}

输出格式

输出最少需要改色的格子数。

样例输入 1

5
RBRBB
RBRRR
RRRBR
RBBRB
BBRBR

样例输出 1

3

样例输入 2

5
RBBBB
BBBBB
BBBBB
BBBBB
BBBBR

样例输出 2

7

数据范围

• $3\le N\le500$；
• 每个格子为 R 或 B；
• $(1,1),(N,N)$ 为红色，$(1,N),(N,1)$ 为蓝色。