解题思路

问题转化

• 可达区域：从起点 $[0, 0]$ 出发，只能走数值为 0 的格子（障碍物 1 无法通过）。
• 不可达区域：包含原生障碍物（值为 1 的格子），以及那些被障碍物“包围”而无法从起点到达的 0 格子。

搜索策略：BFS/DFS

题目内容

设计一个迷宫游戏系列艾尔罗，在设计初期为了方便，使用 $n*n$ 矩阵表示。

$0$ 代表可到达区域，$1$ 表示不可到达区域。

例如有：

[
[0,1,0,0]
[0,0,0,0]
[0,1,0,1]
[0,0,1,0]
]

在这个例子中,因为 $map[3][2]=1$和 $map[2][3] =1$ 。

所以相对于起点 $map[0][0]$ 来说，$map[3][3]$ 的位置是不可达的(只允许左右上下移动)。

为了方便评估设计的艾尔罗迷宫的难易程度，需要有一个方便的算法统计每个迷宫不可到达的网格有多少个。

比如上面的不可达区域为 $4$ 个原生不达的区域加上 $1$ 个衍生的 $map[3][3]$。总数为 $5$ 。

约束：起点统一定义为 $[0.0]$ 。

给定的迷宫二维数组矩阵形式是 $n*n$ ，且 $[0.0]$ 也总是可达(值为 $0$ ),原生不可达的用值 $1$ 表示。

输入描述

第一行一个整数n。 接下来n行，每行都有n个数字(0或1)，每个数字之间以空格分隔。

输出描述

一个整数，表示不可到达的网格有多少个。

样例1

输入

4
0 1 1 0
1 0 0 0
0 1 0 1
0 1 1 0

输出

15

说明

$[0,0]$ 被困，所以都不可达。

样例2

输入

4
0 0 0 0
1 0 0 1
0 0 1 0
0 0 0 1

输出

5

说明

$[2,3]$ 被包围不可达，所以总共是 $4+1=5$ 。

样例3

输入

4
0 0 0 0
0 0 1 0
0 0 1 0
1 0 0 0

输出

3

说明

因为没有被包围/阻碍的，所以总共就是$3$ 。