433. Number of Islands

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且坐标在有效区间内的

代码：