Leetcode-200 Number of Islands

发表于 | 分类于 | 次

Number of Islands

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.

Example 1

1
2
3
4
5
6
7
Input:
11110
11010
11000
00000

Output: 1

Example 2

1
2
3
4
5
6
7
Input:
11000
11000
00100
00011

Output: 3

解题思路

深搜或广搜。如果某个点被访问到，将其状态变为 2，即 grid[i][j]='2'。深搜，相当于单点搜索，其邻节点不一定会在当前层次被展开，因此不用将邻节点的访问状态立即改变。广搜，相当于多点搜索，其邻节点一定会在当前层次被展开，因此需要将邻节点的访问状态立即改变，防止后续节点被重复加入。

复杂度分析

  • 时间复杂度：$O(mn)$，每个点被访问一次。
  • 空间复杂度：$O(mn)$，深搜的递归调用栈，广搜的队列。

代码

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
class Solution_200 {
	int m, n;
	int count = 0;
public:
	int numIslands(vector<vector<char>>& grid) {
		m = grid.size();
		if (0 == m) return 0;
		n = grid[0].size();
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (grid[i][j] !='1') continue;
				//dfs(grid, i, j);
				bfs(grid, i, j);
				count++;
			}
		}
		return count;
	}

	void dfs(vector<vector<char>>& grid, int i, int j) {
		grid[i][j] = '2';
		if (isValid(grid, i - 1, j)) dfs(grid, i - 1, j);
		if (isValid(grid, i + 1, j)) dfs(grid, i + 1, j);
		if (isValid(grid, i, j - 1)) dfs(grid, i, j - 1);
		if (isValid(grid, i, j + 1)) dfs(grid, i, j + 1);
	}

	void bfs(vector<vector<char>>& grid, int i, int j) {
		grid[i][j] = '2';
		queue<int> q;
		q.push(i*n + j);
		while (!q.empty()) {
			int xy = q.front();
			q.pop();
			int x = xy / n, y = xy % n;
			if (isValid(grid, x - 1, y)) {
				//与dfs不同,邻节点在加入队列时就要改变访问状态
				grid[x - 1][y] = '2';
				q.push((x - 1)*n + y);
			}
			if (isValid(grid, x + 1, y)) {
				grid[x + 1][y] = '2';
				q.push((x + 1)*n + y);
			}
			if (isValid(grid, x, y - 1)) {
				grid[x][y - 1] = '2';
				q.push(x*n + y - 1);
			}
			if (isValid(grid, x, y + 1)) {
				grid[x][y + 1] = '2';
				q.push(x*n + y + 1);
			}
		}
	}

	bool isValid(vector<vector<char>>& grid, int i, int j) {
		return (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == '1');
	}
};