1779. 网格
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 有一个 $ n \times n $ 的网格。小火龙在起点 $ S (1,1) $ 处，终点在 $ F (n,n) $ 处，除起点和终点外的格子都会有一个数字 $ 0 $ 或 $ 1 $ 。小火龙从起点开始沿着相邻的格子往终点走，且他走的所有格子只能有一种数字（只有 $ 0 $ 或只有 $ 1 $ ）。注意：小火龙只能更改与起点或终点相邻格子的数字。 请问怎样才使得小火龙不可能走到终点？输出最少的更改次数。 **题目输入保证一开始的时候存在一条全部是 $0$ 或者全部是$1$的通路** - **注意：如果与起点（或终点）相邻的两个格子上的数字是相同的，则从这两个格子出发都满足有一条全部数字都相同的路径** ## 输入格式 第一行包含一个整数 $ n $ （ $ 3 \leq n \leq 200 $ ）。 之后 $ n $ 行包含一个网格。 ## 输出格式 输出一个整数 $ c $ （ $ 0 \leq c \leq 2 $ ）-更改数字的格子数量。 ## 输入 ```in1 4 S010 0001 1000 111F ``` ## 输出 ```out1 1 ``` ```in2 3 S10 111 01F ``` ```out2 2 ``` ## 提示 子任务一： $ 30 $ 分，满足 $ 3\len\le10 $ ； 子任务二： $ 30 $ 分，满足 $ 3\len\le50 $ ； 子任务三： $ 40 $ 分，满足 $ 3\len\le200 $ 。 第一个样例中可以选择更改 $ (3,4) $ ，更改后可能为： `S010` `0001` `1001` `111F` 第二个样例中可以选择更改 $ (1,2) $ 和 $ (2,1) $ ，更改后可能为： `S00` `011` `01F`