问题 6307 --嘉航当总督

6307: 嘉航当总督★★★

时间限制: 1 Sec  内存限制: 256 MB
提交: 35  解决: 18
[提交][状态][命题人:]

题目描述

飞地,一种特殊的人文地理现象,指隶属于某一行政区管辖但不与本区毗连的土地。通辽国总督嘉航希望统计隶属于本国的飞地的数量,请你帮助嘉航完成这件任务。给定一个大小为 n*n 的矩阵 a ,其中 0 代表海洋,1 代表陆地,如果某块陆地经过任意次移动依旧无法与国土(矩阵边界)接壤,那么它就是一块飞地。

一次移动指的是一块陆地往任一方向(上下左右)走到达相邻的另一块陆地。

输入

第一行一个整数 n(1<=n<=300),代表输入矩阵大小;

接下来 n 行,每行 n 个数,其中 0 代表海洋,1 代表陆地。

输出

一个整数,代表飞地的数量。

样例输入
Copy
4
0 0 0 0
1 0 1 0
0 1 1 0
0 0 0 0
样例输出
Copy
3

提示

样例如图所示,有 3 个 1 被 0 包围,无法走到矩阵边界,因此有 3 块飞地。另 1 个 1 在矩阵边界上,因此它不是飞地。

样例输入2

4

0 1 1 0

0 0 1 0

0 0 1 0

0 0 0 0

样例输出2

0

样例2如图所示,所有的 1 都在边界或可到达边界,因此飞地数量为 0。

来源

[提交][状态]