433. Number of Islands
2019-05-28 本文已影响0人
鸭蛋蛋_8441
Description
Given a boolean 2D matrix, 0 is represented as the sea, 1 is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.
Find the number of islands.
Example
Example 1:
Input:
[
[1,1,0,0,0],
[0,1,0,0,1],
[0,0,0,1,1],
[0,0,0,0,0],
[0,0,0,0,1]
]
Output:
3
Example 2:
Input:
[
[1,1]
]
Output:
1
解题思路
在互为邻居的点中, 1只需要被统计一次,才是真正的岛的数目,所以需要用宽度搜索遍历所有值为1的点及其值为1的邻居, 第一次遍历的一个为1的值会被计入岛的数目, 后面它的邻居及邻居的邻居为1的值不应该被统计到岛的数目中去。
每个点的邻居靠坐标差来确定【(0,1),(0,-1),(1,0),(-1,0)】
有效的邻居必须是未被便利过的值为1且坐标在有效区间内的
代码: