题解

本题要求统计迷宫中从起点 [0,0] 出发无法到达的网格数量。迷宫使用 $n \times n$ 矩阵表示，数值 0 表示可到达区域，1 表示原生的不可到达区域（障碍物）。
由于只能进行上下左右移动，我们可以从起点出发利用广度优先搜索（BFS）或深度优先搜索（DFS）将所有能到达的 0 格子标记出来。
最终结果即为矩阵中所有格子数量减去从起点可达的格子数量。

算法思路

问题转化

题目内容

设计一个迷宫游戏系列艾尔罗，在设计初期为了方便，使用 $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$ 。