Coding Spirit

一位程序员,比较帅的那种

0%

Algorithm Puzzles: Number of Islands

Algorithm Puzzles everyday every week sometimes: Number of Islands

Puzzle

Puzzle from leetcode:

Given an m x n 2d grid map of ‘1’s (land) and ‘0’s (water), return 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Example 1:

Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:

Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3

Solving

It looks like a typical depth-first search puzzle:

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
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.size() == 0) return 0;

mSize = grid.size();
nSize = grid[0].size();

int island = 0;

for (int m = 0; m < mSize; ++m) {
for (int n = 0; n < nSize; ++n) {
if (grid[m][n] == '0') {
continue;
} else {
bfs(grid, m, n);
++island;
}
}
}

return island;
}

private:
int mSize;
int nSize;
void bfs(vector<vector<char>>& grid, int m, int n) {
if (m < 0 || n < 0 || m >= mSize || n >= nSize || grid[m][n] != '1')
return;

grid[m][n] = '0';
bfs(grid, m + 1, n);
bfs(grid, m - 1, n);
bfs(grid, m, n + 1);
bfs(grid, m, n - 1);
}
};