LeetCode 200: Number of Islands (DFS / BFS Flood Fill)
LeetCode 200MatrixDFSBFSToday we solve LeetCode 200 - Number of Islands.
Source: https://leetcode.com/problems/number-of-islands/
English
Problem Summary
Given a 2D grid of '1' (land) and '0' (water), count how many islands exist. An island is formed by horizontally or vertically adjacent land cells.
Key Insight
Every time we find an unvisited land cell, we discovered a new island. Immediately run DFS/BFS flood fill to mark the entire connected component, so it will not be counted again.
Brute Force and Limitations
A naive approach might repeatedly search neighbors without proper visited marking, causing duplicated work and potentially O((mn)^2) behavior on dense grids. We need one-pass traversal with component marking.
Optimal Algorithm Steps
1) Iterate all cells in the grid.
2) If current cell is water, continue.
3) If current cell is land, increment island count.
4) Start DFS/BFS from this cell and mark all reachable land as visited (for example, mutate to '0').
5) Continue scanning until all cells are processed.
6) Return the final island count.
Complexity Analysis
Time: O(mn), each cell is visited at most once.
Space: O(mn) worst case due to recursion stack/queue when the whole grid is land.
Common Pitfalls
- Forgetting to mark visited cells, causing repeated counting.
- Using diagonal adjacency (problem only allows 4 directions).
- Out-of-bound checks written in wrong order.
- Recursive DFS stack overflow on very large grids (iterative BFS/DFS can avoid this).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int numIslands(char[][] grid) {
int m = grid.length, n = grid[0].length;
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
private void dfs(char[][] grid, int r, int c) {
int m = grid.length, n = grid[0].length;
if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] == '0') return;
grid[r][c] = '0';
dfs(grid, r + 1, c);
dfs(grid, r - 1, c);
dfs(grid, r, c + 1);
dfs(grid, r, c - 1);
}
}func numIslands(grid [][]byte) int {
m, n := len(grid), len(grid[0])
count := 0
var dfs func(int, int)
dfs = func(r, c int) {
if r < 0 || c < 0 || r >= m || c >= n || grid[r][c] == '0' {
return
}
grid[r][c] = '0'
dfs(r+1, c)
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' {
count++
dfs(i, j)
}
}
}
return count
}class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
int count = 0;
function<void(int,int)> dfs = [&](int r, int c) {
if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] == '0') return;
grid[r][c] = '0';
dfs(r + 1, c);
dfs(r - 1, c);
dfs(r, c + 1);
dfs(r, c - 1);
};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
count++;
dfs(i, j);
}
}
}
return count;
}
};class Solution:
def numIslands(self, grid: list[list[str]]) -> int:
m, n = len(grid), len(grid[0])
count = 0
def dfs(r: int, c: int) -> None:
if r < 0 or c < 0 or r >= m or c >= n or grid[r][c] == '0':
return
grid[r][c] = '0'
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
count += 1
dfs(i, j)
return countvar numIslands = function(grid) {
const m = grid.length;
const n = grid[0].length;
let count = 0;
const dfs = (r, c) => {
if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] === '0') return;
grid[r][c] = '0';
dfs(r + 1, c);
dfs(r - 1, c);
dfs(r, c + 1);
dfs(r, c - 1);
};
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;
};中文
题目概述
给定一个由 '1'（陆地）和 '0'（海水）组成的二维网格，统计岛屿数量。岛屿由上下左右相邻的陆地连接形成。
核心思路
扫描网格时，每遇到一个尚未访问的陆地，就说明发现了一个新岛屿。随后立刻做一次 DFS/BFS 泛洪，把该连通块全部标记，避免重复计数。
暴力解法与不足
如果不及时标记访问状态，可能会反复从同一块陆地出发，产生大量重复搜索，效率明显下降。正确做法是“发现即淹没/标记”。
最优算法步骤
1）遍历网格每个位置。
2）如果是水，跳过。
3）如果是陆地，岛屿计数加一。
4）从该点出发做 DFS/BFS，把同一岛屿上的陆地都改成 '0'（或 visited=true）。
5）继续遍历直到结束。
6）返回计数结果。
复杂度分析
时间复杂度：O(mn)，每个格子最多访问一次。
空间复杂度：O(mn)（最坏情况下递归栈或队列可能达到网格规模）。
常见陷阱
- 忘记标记访问，导致重复计数。
- 错把对角线也算连通（题目仅上下左右）。
- 越界判断顺序错误导致运行异常。
- 大网格用递归可能栈溢出，可改用迭代 BFS/DFS。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int numIslands(char[][] grid) {
int m = grid.length, n = grid[0].length;
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
private void dfs(char[][] grid, int r, int c) {
int m = grid.length, n = grid[0].length;
if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] == '0') return;
grid[r][c] = '0';
dfs(grid, r + 1, c);
dfs(grid, r - 1, c);
dfs(grid, r, c + 1);
dfs(grid, r, c - 1);
}
}func numIslands(grid [][]byte) int {
m, n := len(grid), len(grid[0])
count := 0
var dfs func(int, int)
dfs = func(r, c int) {
if r < 0 || c < 0 || r >= m || c >= n || grid[r][c] == '0' {
return
}
grid[r][c] = '0'
dfs(r+1, c)
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' {
count++
dfs(i, j)
}
}
}
return count
}class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
int count = 0;
function<void(int,int)> dfs = [&](int r, int c) {
if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] == '0') return;
grid[r][c] = '0';
dfs(r + 1, c);
dfs(r - 1, c);
dfs(r, c + 1);
dfs(r, c - 1);
};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
count++;
dfs(i, j);
}
}
}
return count;
}
};class Solution:
def numIslands(self, grid: list[list[str]]) -> int:
m, n = len(grid), len(grid[0])
count = 0
def dfs(r: int, c: int) -> None:
if r < 0 or c < 0 or r >= m or c >= n or grid[r][c] == '0':
return
grid[r][c] = '0'
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
count += 1
dfs(i, j)
return countvar numIslands = function(grid) {
const m = grid.length;
const n = grid[0].length;
let count = 0;
const dfs = (r, c) => {
if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] === '0') return;
grid[r][c] = '0';
dfs(r + 1, c);
dfs(r - 1, c);
dfs(r, c + 1);
dfs(r, c - 1);
};
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;
};
Comments