NumberOfIslands [岛屿数量]
# 问题
给定一个由 0 和 1 组成的 2 维数组矩阵，计算 1 的岛屿的数量。一个岛被一组相邻的单元格所包围，这些单元格都是 1。一个单元格只能在水平和垂直方向上相邻。
input: binaryMatrix = [ [0, 1, 0, 1, 0],
[0, 0, 1, 1, 1],
[1, 0, 0, 1, 0],
[0, 1, 1, 0, 0],
[1, 0, 1, 0, 1] ]
output: 6 # there are six islands
1
2
3
4
5
6
7
2
3
4
5
6
7
# 伪代码
def main():
visited [] # array to keep track of visited cell
num_islands = 0 # start with zero
for each row, col in matrix
num_island += get_number_of_islands(matrix, row, col) #return 1 if it is an island
return num_island
def get_number_of_islands(matrix, row, col, visited):
check if row and col is out of bound of the matrix
check if we already visited the cell with row, col
check if the cell is 0
=> return 0
mark the cell as visited in the visited array
recursive call get_number_of_islands() on each adjacent cell
return 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 实现
# JavaScript
/* Number of Islands
https://dev.to/rattanakchea/amazons-interview-question-count-island-21h6
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
a two dimensional grid map
each element is going to represent a piece of land
1 is land,
0 is water
output a number which is the number of islands
Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3
I: two dimensional array
O: a single integer; total number of islands
Pseudocode:
OUTER FUNCTION
set count to 0
INNER FUNCTION - flood (col, row)
if the tile is water
return
make tile water(flood tile)
invoke flood on the neighbor coordinates
iterate over the matrix (col, row)
if the current element is a 1
increment count
invoke flood (coordinates for col and row)
Return the count
*/
const islands = (matrixGrid) => {
const matrix = matrixGrid
let counter = 0
const flood = (row, col) => {
if (row < 0 || col < 0) return // Off the map above or left
if (row >= matrix.length || col >= matrix[row].length) return // Off the map below or right
const tile = matrix[row][col]
if (tile !== '1') return
matrix[row][col] = '0'
flood(row + 1, col) // Down
flood(row - 1, col) // Up
flood(row, col + 1) // Right
flood(row, col - 1) // Left
}
for (let row = 0; row < matrix.length; row += 1) {
for (let col = 0; col < matrix[row].length; col += 1) {
const current = matrix[row][col]
if (current === '1') {
flood(row, col)
counter += 1
}
}
}
return counter
}
// islands(
// ['1', '1', '0', '0', '0'],
// ['1', '1', '0', '0', '0'],
// ['0', '0', '1', '0', '0'],
// ['0', '0', '0', '1', '1']
// )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
# Python
def get_number_of_islands(binaryMatrix):
rows = len(binaryMatrix)
cols = len(binaryMatrix[0])
# you can use Set if you like
# or change the content of binaryMatrix as it is visited
visited = [[0 for col in range(cols)] for r in range(rows)]
number_of_island = 0
for row in range(rows):
for col in range(cols):
number_of_island += get_island(binaryMatrix, row, col, visited)
return number_of_island
# get a continuous island
def get_island(binaryMatrix, row, col, visited):
if not is_valid(binaryMatrix, row, col)
or visited[row][col] == 1 or binaryMatrix[row][col] == 0:
return 0
# mark as visited
visited[row][col] = 1
get_island(binaryMatrix, row, col + 1, visited)
get_island(binaryMatrix, row, col - 1, visited)
get_island(binaryMatrix, row + 1, col, visited)
get_island(binaryMatrix, row - 1, col, visited)
return 1
def is_valid(binaryMatrix, row, col):
rows = len(binaryMatrix)
cols = len(binaryMatrix[0])
return row >= 0 and row < rows and col >= 0 and col < cols
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 参考
编辑 (opens new window)
上次更新: 2022/10/18, 19:00:15
Gitalking ...