200. 岛屿数量
题目描述
输入一个 m x n 的二维网格 grid，每个格子是字符 '1'（陆地）或 '0'（水）。
上下左右相邻的陆地格子属于同一座岛，斜向相邻不算相连。每座岛四周都是水，网格外部也都视为水。
返回网格中岛屿的个数。
示例 1
输入：grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]] 输出：1
解释：所有陆地格子彼此连通，只有 1 座岛。
示例 2
输入：grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]] 输出：3
解释：左上角 2×2 的陆地是一座，中间单独的 '1' 是一座，右下角两个 '1' 是一座，共 3 座。
数据范围
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]为'0'或'1'。
解题思路：广度优先搜索
用队列或集合维护图上的可达状态。
为什么正确
状态队列中的元素不会重复处理。
复杂度分析
时间 O(mn)，额外空间 O(min(m,n))。
易错点
注意边界条件并在回溯或弹出后恢复状态。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
from collections import deque
class Solution:
def numIslands(self, grid):
if not grid:
return 0
m, n = len(grid), len(grid[0])
count = 0
for r in range(m):
for c in range(n):
if grid[r][c] == '1':
count += 1
grid[r][c] = '0'
queue = deque([(r, c)])
while queue:
x, y = queue.popleft()
for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
grid[nx][ny] = '0'
queue.append((nx, ny))
return countclass Solution {
public int numIslands(char[][] grid) {
if (grid.length == 0) {
return 0;
}
int m = grid.length, n = grid[0].length;
int count = 0;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == '1') {
count++;
grid[r][c] = '0';
Deque<int[]> queue = new ArrayDeque<>();
queue.add(new int[]{r, c});
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int x = cur[0], y = cur[1];
for (int[] d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (0 <= nx && nx < m && 0 <= ny && ny < n && grid[nx][ny] == '1') {
grid[nx][ny] = '0';
queue.add(new int[]{nx, ny});
}
}
}
}
}
}
return count;
}
}class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.empty()) {
return 0;
}
int m = grid.size(), n = grid[0].size();
int count = 0;
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == '1') {
count++;
grid[r][c] = '0';
queue<pair<int, int>> q;
q.push({r, c});
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (auto& d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (0 <= nx && nx < m && 0 <= ny && ny < n && grid[nx][ny] == '1') {
grid[nx][ny] = '0';
q.push({nx, ny});
}
}
}
}
}
}
return count;
}
};func numIslands(grid [][]byte) int {
if len(grid) == 0 {
return 0
}
m, n := len(grid), len(grid[0])
count := 0
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
if grid[r][c] == '1' {
count++
grid[r][c] = '0'
queue := [][2]int{{r, c}}
for len(queue) > 0 {
x, y := queue[0][0], queue[0][1]
queue = queue[1:]
for _, d := range dirs {
nx, ny := x+d[0], y+d[1]
if 0 <= nx && nx < m && 0 <= ny && ny < n && grid[nx][ny] == '1' {
grid[nx][ny] = '0'
queue = append(queue, [2]int{nx, ny})
}
}
}
}
}
}
return count
}var numIslands = function(grid) {
if (!grid.length) {
return 0;
}
const m = grid.length, n = grid[0].length;
let count = 0;
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (grid[r][c] === '1') {
count++;
grid[r][c] = '0';
const queue = [[r, c]];
for (let h = 0; h < queue.length; h++) {
const [x, y] = queue[h];
for (const [dx, dy] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const nx = x + dx, ny = y + dy;
if (0 <= nx && nx < m && 0 <= ny && ny < n && grid[nx][ny] === '1') {
grid[nx][ny] = '0';
queue.push([nx, ny]);
}
}
}
}
}
}
return count;
};function numIslands(grid: string[][]): number {
if (!grid.length) {
return 0;
}
const m = grid.length, n = grid[0].length;
let count = 0;
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (grid[r][c] === '1') {
count++;
grid[r][c] = '0';
const queue = [[r, c]];
for (let h = 0; h < queue.length; h++) {
const [x, y] = queue[h];
for (const [dx, dy] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const nx = x + dx, ny = y + dy;
if (0 <= nx && nx < m && 0 <= ny && ny < n && grid[nx][ny] === '1') {
grid[nx][ny] = '0';
queue.push([nx, ny]);
}
}
}
}
}
}
return count;
};其他解法
BFS 和 DFS 都是从一块陆地出发“淘污”整座岛，只是扩展顺序不同，DFS 可能递归很深；并查集把问题看成统计连通分量的个数，通过合并相邻陆地得到答案。
解法 2：深度优先搜索 时间 O(mn)，空间 O(mn)
扫描网格，遇到 '1' 就把岛屿数加一，并从这里递归地向上下左右扩展，把连通的 '1' 全部改成 '0'。递归遇到越界或 '0' 时返回。这样每座岛屿只会被计数一次。
代码最短，不需要队列。最坏情况下整张网格都是陆地，递归深度可达 mn，有栈溢出的风险。
import sys
from typing import List
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
sys.setrecursionlimit(max(10000, len(grid) * len(grid[0]) + 100))
m, n = len(grid), len(grid[0])
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
return
grid[i][j] = '0'
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
count += 1
dfs(i, j)
return countclass Solution {
private void dfs(char[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') return;
grid[i][j] = '0';
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
public int numIslands(char[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
}class Solution {
void dfs(vector<vector<char>>& grid, int i, int j) {
if (i < 0 || i >= (int)grid.size() || j < 0 || j >= (int)grid[0].size() || grid[i][j] != '1') return;
grid[i][j] = '0';
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
public:
int numIslands(vector<vector<char>>& grid) {
int count = 0;
for (int i = 0; i < (int)grid.size(); i++) {
for (int j = 0; j < (int)grid[0].size(); j++) {
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
};func numIslands(grid [][]byte) int {
m, n := len(grid), len(grid[0])
var dfs func(i, j int)
dfs = func(i, j int) {
if i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1' {
return
}
grid[i][j] = '0'
dfs(i+1, j)
dfs(i-1, j)
dfs(i, j+1)
dfs(i, j-1)
}
count := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' {
count++
dfs(i, j)
}
}
}
return count
}var numIslands = function(grid) {
const m = grid.length, n = grid[0].length;
const dfs = (i, j) => {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] !== '1') return;
grid[i][j] = '0';
dfs(i + 1, j);
dfs(i - 1, j);
dfs(i, j + 1);
dfs(i, j - 1);
};
let count = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === '1') {
count++;
dfs(i, j);
}
}
}
return count;
};function numIslands(grid: string[][]): number {
const m = grid.length, n = grid[0].length;
const dfs = (i: number, j: number): void => {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] !== '1') return;
grid[i][j] = '0';
dfs(i + 1, j);
dfs(i - 1, j);
dfs(i, j + 1);
dfs(i, j - 1);
};
let count = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === '1') {
count++;
dfs(i, j);
}
}
}
return count;
};解法 3：并查集 时间 O(mn·α(mn))，空间 O(mn)
把每个格子编号为 i*n+j，初始时每个陆地各自成一个集合，岛屿数 count 等于陆地格子数。再遍历每个陆地，如果右边或下边也是陆地，就把两个格子合并；每次成功合并两个不同集合，count 减一。最后的 count 就是岛屿数。
不修改原网格，也不需要搜索，并且可以自然推广到陆地动态增加的场景（如第 305 题）。需要实现并查集，代码更长。
from typing import List
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
parent = list(range(m * n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
count = sum(row.count('1') for row in grid)
for i in range(m):
for j in range(n):
if grid[i][j] != '1':
continue
for x, y in ((i + 1, j), (i, j + 1)):
if x < m and y < n and grid[x][y] == '1':
ra, rb = find(i * n + j), find(x * n + y)
if ra != rb:
parent[ra] = rb
count -= 1
return countclass Solution {
private int[] parent;
private int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public int numIslands(char[][] grid) {
int m = grid.length, n = grid[0].length;
parent = new int[m * n];
for (int i = 0; i < m * n; i++) parent[i] = i;
int count = 0;
for (char[] row : grid)
for (char c : row)
if (c == '1') count++;
int[] dx = {1, 0}, dy = {0, 1};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != '1') continue;
for (int d = 0; d < 2; d++) {
int x = i + dx[d], y = j + dy[d];
if (x < m && y < n && grid[x][y] == '1') {
int ra = find(i * n + j), rb = find(x * n + y);
if (ra != rb) {
parent[ra] = rb;
count--;
}
}
}
}
}
return count;
}
}class Solution {
vector<int> parent;
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
parent.resize(m * n);
for (int i = 0; i < m * n; i++) parent[i] = i;
int count = 0;
for (auto& row : grid)
for (char c : row)
if (c == '1') count++;
int dx[2] = {1, 0}, dy[2] = {0, 1};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != '1') continue;
for (int d = 0; d < 2; d++) {
int x = i + dx[d], y = j + dy[d];
if (x < m && y < n && grid[x][y] == '1') {
int ra = find(i * n + j), rb = find(x * n + y);
if (ra != rb) {
parent[ra] = rb;
count--;
}
}
}
}
}
return count;
}
};func numIslands(grid [][]byte) int {
m, n := len(grid), len(grid[0])
parent := make([]int, m*n)
for i := range parent {
parent[i] = i
}
find := func(x int) int {
for parent[x] != x {
parent[x] = parent[parent[x]]
x = parent[x]
}
return x
}
count := 0
for _, row := range grid {
for _, c := range row {
if c == '1' {
count++
}
}
}
dirs := [][2]int{{1, 0}, {0, 1}}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] != '1' {
continue
}
for _, d := range dirs {
x, y := i+d[0], j+d[1]
if x < m && y < n && grid[x][y] == '1' {
ra, rb := find(i*n+j), find(x*n+y)
if ra != rb {
parent[ra] = rb
count--
}
}
}
}
}
return count
}var numIslands = function(grid) {
const m = grid.length, n = grid[0].length;
const parent = Array.from({ length: m * n }, (_, i) => i);
const find = (x) => {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
let count = 0;
for (const row of grid) for (const c of row) if (c === '1') count++;
const dirs = [[1, 0], [0, 1]];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] !== '1') continue;
for (const [dx, dy] of dirs) {
const x = i + dx, y = j + dy;
if (x < m && y < n && grid[x][y] === '1') {
const ra = find(i * n + j), rb = find(x * n + y);
if (ra !== rb) {
parent[ra] = rb;
count--;
}
}
}
}
}
return count;
};function numIslands(grid: string[][]): number {
const m = grid.length, n = grid[0].length;
const parent = Array.from({ length: m * n }, (_, i) => i);
const find = (x: number): number => {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
let count = 0;
for (const row of grid) for (const c of row) if (c === '1') count++;
const dirs = [[1, 0], [0, 1]];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] !== '1') continue;
for (const [dx, dy] of dirs) {
const x = i + dx, y = j + dy;
if (x < m && y < n && grid[x][y] === '1') {
const ra = find(i * n + j), rb = find(x * n + y);
if (ra !== rb) {
parent[ra] = rb;
count--;
}
}
}
}
}
return count;
};