rt

网格
时间限制：C/C++ 1000MS，其他语言 2000MS
内存限制：C/C++ 256MB，其他语言 512MB
分数：100
描述

有一个 n×n 的网格，小海狸在起点 S(1,1) 处，终点在 F(n,n) 处，除起点和终点外的格子都会有一个数字0或1。小海狸从起点开始沿着相邻的格子往终点走，且他走的所有格子只能有一种数字（只有0或只有1）。
注意：小海狸只能更改与起点或终点相邻格子的数字。请问怎样才使得小海狸不可能走到终点？输出最少的更改次数。

题目输入保证一开始的时候存在一条全部是0或者全部是1的通路

输入描述

输入
第一行包含一个整数 n(3≤n≤200) 。
之后 n 行包含一个网格。

输出描述

输出
输出一个整数 c(0≤c≤2)-更改数字的格子数量。

用例输入 1 

4
S010
0001
1000
111F
用例输出 1 

1
用例输入 2 

3
S10
111
01F
用例输出 2 

2
提示

子任务一: 30 分, 满足 3≤n≤10;
子任务二：30分，满足 3≤n≤50 ；
子任务三：40分, 满足 3≤n≤200 。
第一个样例中可以选择更改 (3,4), 更改后可能为:
S010
0001
1001
111F
第二个样例中可以选择更改 (1,2) 和 (2,1), 更改后可能为:
S00
011
01F