# 200. Number of Islands 岛屿数量

@TOC

## # 题目描述

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:

``````Input:
11110
11010
11000
00000

Output: 1
``````

Example 2:

``````Input:
11000
11000
00100
00011

Output: 3
``````

## # 解题方法

### # DFS

``````class Solution:
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
res = 0
for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == "1":
self.dfs(grid, r, c)
res += 1
return res

def dfs(self, grid, i, j):
dirs = [[-1, 0], [0, 1], [0, -1], [1, 0]]
grid[i][j] = "0"
for dir in dirs:
nr, nc = i + dir[0], j + dir[1]
if nr >= 0 and nc >= 0 and nr < len(grid) and nc < len(grid[0]):
if grid[nr][nc] == "1":
self.dfs(grid, nr, nc)
``````

C++版本的代码如下：

``````class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.empty() || grid[0].empty())
return 0;
const int M = grid.size();
const int N = grid[0].size();
int res = 0;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (grid[i][j] == '1') {
res ++;
dfs(grid, i, j);
}
}
}
return res;
}
void dfs(vector<vector<char>>& grid, int x, int y) {
grid[x][y] = '0';
const int M = grid.size();
const int N = grid[0].size();
for (auto& dir : dirs) {
int nx = x + dir[0];
int ny = y + dir[1];
if (nx < 0 || nx >= M || ny < 0 || ny >= N || grid[nx][ny] == '0')
continue;
dfs(grid, nx, ny);
}
}
private:
vector<vector<int>> dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
};
``````

### # BFS

Python 代码如下：

``````class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if not grid or not grid[0]: return 0
M, N = len(grid), len(grid[0])
que = collections.deque()
res = 0
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for i in range(M):
for j in range(N):
if grid[i][j] == '1':
res += 1
grid[i][j] = '0'
que.append((i, j))
while que:
x, y = que.pop()
for d in directions:
nx, ny = x + d[0], y + d[1]
if 0 <= nx < M and 0 <= ny < N and grid[nx][ny] == '1':
grid[nx][ny] = '0'
que.append((nx, ny))
return res
``````

C++代码如下：

``````class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.size() == 0 || grid[0].size() == 0) return 0;
const int M = grid.size(), N = grid[0].size();
int res = 0;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (grid[i][j] == '1') {
++res;
bfs(grid, i, j);
}
}
}
return res;
}
// gird[x][y] = 1, delete it and its around.
void bfs(vector<vector<char>>& grid, int x, int y) {
const int M = grid.size(), N = grid[0].size();
queue<pair<int, int>> q;
q.push({x, y});
while (!q.empty()) {
if (grid[x][y] != '1') continue;
grid[x][y] = '0';
for (auto d : dirs) {
int i = x + d.first;
int j = y + d.second;
if (i < 0 || i >= M || j < 0 || j >= N || grid[i][j] != '1') {
continue;
}
q.push({i, j});
}
}
}
private:
vector<pair<int, int>> dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
};
``````

## # 日期

2018 年 7 月 20 日 —— 北京的阴雨天，又闷又潮 2019 年 1 月 8 日 —— 别熬夜，我都开始有黑眼圈了。。 2020 年 4 月 20 日 —— 没想到我也会熬夜看剧