0%

[Leetcode]200. Number of Islands(C++)

题目描述

题目链接:200. Number of Islands

Given an m x n 2D binary grid grid which represents a 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

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

例子 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

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'.

解题思路

使用一个等大的数组来作为遍历过的 1 的位置,然后遍历 grid,每发现一个未被标志过的 1 则表示发现一个新的岛屿, 对所有 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
#include <vector>

class Solution {
public:
int numIslands(std::vector<std::vector<char>>& grid) {
int m = grid.size();
int n = grid[0].size();

std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false));
int result = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (!visited[i][j] && grid[i][j] == '1') {
result++;
visited[i][j] = true;
dfs(grid, i, j, visited);
}
}
}

return result;
}

private:
void dfs(const std::vector<std::vector<char>>& grid, int row, int col,
std::vector<std::vector<bool>>& visited) {
std::vector<std::pair<int, int>> dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

for (auto& dir : dirs) {
int r = row + dir.first;
int c = col + dir.second;

if (r < 0 || c < 0 || r >= grid.size() || c >= grid[0].size()) {
continue;
}

if (grid[r][c] == '1' && !visited[r][c]) {
visited[r][c] = true;
dfs(grid, r, c, visited);
}
}
}
};
  • 时间复杂度: O(mn)
  • 空间复杂度: O(mn)

GitHub 代码同步地址: 200.NumberOfIslands.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions