1254. 统计封闭岛屿的数目

中等图论逐岛搜索并判断是否碰到边界力扣原题 ↗

题目描述

输入二维矩阵 grid，0 表示陆地，1 表示水。

上下左右相连的陆地组成的极大区域称为一座岛。如果一座岛的上、下、左、右四个方向都被水包围，也就是它没有任何格子在矩阵边界上，就称它为封闭岛。

返回封闭岛的个数。

示例 1

输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出：2

解释：左侧那一大块陆地和 (3,6) 这一格陆地被水围住；最右列贴边的陆地不算。

示例 2

输入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
输出：1

解释：只有中间 (1,2) 这一格陆地被水完全包围。

示例 3

输入：grid = [[1,1,1,1,1,1,1],[1,0,0,0,0,0,1],[1,0,1,1,1,0,1],[1,0,1,0,1,0,1],[1,0,1,1,1,0,1],[1,0,0,0,0,0,1],[1,1,1,1,1,1,1]]
输出：2

解释：外圈的环形陆地和正中央的一格陆地都是封闭岛。

数据范围

1 <= grid.length, grid[0].length <= 100
0 <= grid[i][j] <= 1

解题思路：逐岛搜索并判断是否碰到边界

一座岛不封闭，当且仅当它有格子落在矩阵边界上。逐格扫描，遇到未访问的 0 就用栈 DFS 把整座岛走完，访问后改成 1 防止重复。DFS 过程中只要有任何格子在第一行、最后一行、第一列或最后一列，就把 closed 设为 false。整座岛走完后，closed 仍为 true 才计数。

为什么正确

每次 DFS 结束时，这座岛的所有格子都已改成 1；closed 为 true 当且仅当这座岛没有任何格子在边界上。

复杂度分析

时间 O(m·n)：每个格子最多入栈一次。空间 O(m·n)（栈）。

易错点

发现岛碰到边界后不能立即停止 DFS，必须把整座岛走完并标记，否则剩下的格子会在之后的扫描中被误当成新岛，可能被错误地算作封闭岛。注意本题中 0 是陆地、1 是水，与常见题目相反。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        count = 0
        for r in range(m):
            for c in range(n):
                if grid[r][c] != 0:
                    continue
                grid[r][c] = 1
                stack = [(r, c)]
                closed = True
                while stack:
                    x, y = stack.pop()
                    if x == 0 or y == 0 or x == m - 1 or y == n - 1:
                        closed = False
                    for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0:
                            grid[nx][ny] = 1
                            stack.append((nx, ny))
                if closed:
                    count += 1
        return count

class Solution {
    public int closedIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int count = 0;
        int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] != 0) {
                    continue;
                }
                grid[r][c] = 1;
                Deque<int[]> stack = new ArrayDeque<>();
                stack.push(new int[]{r, c});
                boolean closed = true;
                while (!stack.isEmpty()) {
                    int[] p = stack.pop();
                    int x = p[0], y = p[1];
                    if (x == 0 || y == 0 || x == m - 1 || y == n - 1) {
                        closed = false;
                    }
                    for (int d = 0; d < 4; d++) {
                        int nx = x + dx[d], ny = y + dy[d];
                        if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                            grid[nx][ny] = 1;
                            stack.push(new int[]{nx, ny});
                        }
                    }
                }
                if (closed) {
                    count++;
                }
            }
        }
        return count;
    }
}

class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int count = 0;
        int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] != 0) {
                    continue;
                }
                grid[r][c] = 1;
                vector<pair<int,int>> stk = {{r, c}};
                bool closed = true;
                while (!stk.empty()) {
                    auto [x, y] = stk.back(); stk.pop_back();
                    if (x == 0 || y == 0 || x == m - 1 || y == n - 1) {
                        closed = false;
                    }
                    for (int d = 0; d < 4; d++) {
                        int nx = x + dx[d], ny = y + dy[d];
                        if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                            grid[nx][ny] = 1;
                            stk.push_back({nx, ny});
                        }
                    }
                }
                if (closed) {
                    count++;
                }
            }
        }
        return count;
    }
};

func closedIsland(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	count := 0
	dx := []int{1, -1, 0, 0}
	dy := []int{0, 0, 1, -1}
	for r := 0; r < m; r++ {
		for c := 0; c < n; c++ {
			if grid[r][c] != 0 {
				continue
			}
			grid[r][c] = 1
			stack := [][2]int{{r, c}}
			closed := true
			for len(stack) > 0 {
				p := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				x, y := p[0], p[1]
				if x == 0 || y == 0 || x == m-1 || y == n-1 {
					closed = false
				}
				for d := 0; d < 4; d++ {
					nx, ny := x+dx[d], y+dy[d]
					if nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 0 {
						grid[nx][ny] = 1
						stack = append(stack, [2]int{nx, ny})
					}
				}
			}
			if closed {
				count++
			}
		}
	}
	return count
}

var closedIsland = function(grid) {
    const m = grid.length, n = grid[0].length;
    let count = 0;
    const D = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] !== 0) {
                continue;
            }
            grid[r][c] = 1;
            const stack = [[r, c]];
            let closed = true;
            while (stack.length > 0) {
                const [x, y] = stack.pop();
                if (x === 0 || y === 0 || x === m - 1 || y === n - 1) {
                    closed = false;
                }
                for (const [a, b] of D) {
                    const nx = x + a, ny = y + b;
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === 0) {
                        grid[nx][ny] = 1;
                        stack.push([nx, ny]);
                    }
                }
            }
            if (closed) {
                count++;
            }
        }
    }
    return count;
};

function closedIsland(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    let count = 0;
    const D = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] !== 0) {
                continue;
            }
            grid[r][c] = 1;
            const stack = [[r, c]];
            let closed = true;
            while (stack.length > 0) {
                const [x, y] = stack.pop()!;
                if (x === 0 || y === 0 || x === m - 1 || y === n - 1) {
                    closed = false;
                }
                for (const [a, b] of D) {
                    const nx = x + a, ny = y + b;
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === 0) {
                        grid[nx][ny] = 1;
                        stack.push([nx, ny]);
                    }
                }
            }
            if (closed) {
                count++;
            }
        }
    }
    return count;
}

载入编辑器，自己跑一遍 →

其他解法

主解法在一次搜索中同时完成标记和判断，必须把整个岛屿搜完才能下结论；先淹没边界的做法先排除所有不合格的陆地，剩下的就是普通的岛屿计数。两者复杂度相同。

解法 2：先淹没边界岛屿再计数时间 O(mn)，空间 O(mn)

与边界相连的陆地一定不属于封闭岛屿。先从网格四条边上的每个陆地格出发做深度优先搜索，把和它们连通的陆地全部标记为水。此时剩下的每个连通块都不碰边界，再按普通的岛屿计数方法统计连通块个数即可。

把问题拆成“去掉不合格的”和“数岛屿”两个独立步骤，第二步不再需要在搜索中维护是否封闭的标记。这是「飞地的数量」「被围绕的区域」等题的通用套路。需要多写一轮边界循环。

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def sink(r, c):
            stack = [(r, c)]
            grid[r][c] = 1
            while stack:
                x, y = stack.pop()
                for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0:
                        grid[nx][ny] = 1
                        stack.append((nx, ny))

        for r in range(m):
            for c in range(n):
                if (r == 0 or c == 0 or r == m - 1 or c == n - 1) and grid[r][c] == 0:
                    sink(r, c)
        count = 0
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 0:
                    sink(r, c)
                    count += 1
        return count

class Solution {
    void sink(int[][] grid, int r, int c) {
        int m = grid.length, n = grid[0].length;
        int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
        Deque<int[]> stack = new ArrayDeque<>();
        stack.push(new int[]{r, c});
        grid[r][c] = 1;
        while (!stack.isEmpty()) {
            int[] cur = stack.pop();
            for (int d = 0; d < 4; d++) {
                int nx = cur[0] + dx[d], ny = cur[1] + dy[d];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                    grid[nx][ny] = 1;
                    stack.push(new int[]{nx, ny});
                }
            }
        }
    }

    public int closedIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if ((r == 0 || c == 0 || r == m - 1 || c == n - 1) && grid[r][c] == 0) sink(grid, r, c);
            }
        }
        int count = 0;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 0) {
                    sink(grid, r, c);
                    count++;
                }
            }
        }
        return count;
    }
}

class Solution {
public:
    void sink(vector<vector<int>>& grid, int r, int c) {
        int m = grid.size(), n = grid[0].size();
        int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
        vector<pair<int, int>> stk = {{r, c}};
        grid[r][c] = 1;
        while (!stk.empty()) {
            auto [x, y] = stk.back();
            stk.pop_back();
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                    grid[nx][ny] = 1;
                    stk.push_back({nx, ny});
                }
            }
        }
    }

    int closedIsland(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if ((r == 0 || c == 0 || r == m - 1 || c == n - 1) && grid[r][c] == 0) sink(grid, r, c);
            }
        }
        int count = 0;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 0) {
                    sink(grid, r, c);
                    count++;
                }
            }
        }
        return count;
    }
};

func closedIsland(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	dirs := [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	sink := func(r, c int) {
		stack := [][2]int{{r, c}}
		grid[r][c] = 1
		for len(stack) > 0 {
			cur := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			for _, d := range dirs {
				nx, ny := cur[0]+d[0], cur[1]+d[1]
				if nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 0 {
					grid[nx][ny] = 1
					stack = append(stack, [2]int{nx, ny})
				}
			}
		}
	}
	for r := 0; r < m; r++ {
		for c := 0; c < n; c++ {
			if (r == 0 || c == 0 || r == m-1 || c == n-1) && grid[r][c] == 0 {
				sink(r, c)
			}
		}
	}
	count := 0
	for r := 0; r < m; r++ {
		for c := 0; c < n; c++ {
			if grid[r][c] == 0 {
				sink(r, c)
				count++
			}
		}
	}
	return count
}

var closedIsland = function(grid) {
    const m = grid.length, n = grid[0].length;
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    const sink = (r, c) => {
        const stack = [[r, c]];
        grid[r][c] = 1;
        while (stack.length) {
            const [x, y] = stack.pop();
            for (const [dx, dy] of dirs) {
                const nx = x + dx, ny = y + dy;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === 0) {
                    grid[nx][ny] = 1;
                    stack.push([nx, ny]);
                }
            }
        }
    };
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if ((r === 0 || c === 0 || r === m - 1 || c === n - 1) && grid[r][c] === 0) sink(r, c);
        }
    }
    let count = 0;
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === 0) {
                sink(r, c);
                count++;
            }
        }
    }
    return count;
};

function closedIsland(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    const sink = (r: number, c: number): void => {
        const stack: number[][] = [[r, c]];
        grid[r][c] = 1;
        while (stack.length) {
            const [x, y] = stack.pop()!;
            for (const [dx, dy] of dirs) {
                const nx = x + dx, ny = y + dy;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === 0) {
                    grid[nx][ny] = 1;
                    stack.push([nx, ny]);
                }
            }
        }
    };
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if ((r === 0 || c === 0 || r === m - 1 || c === n - 1) && grid[r][c] === 0) sink(r, c);
        }
    }
    let count = 0;
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === 0) {
                sink(r, c);
                count++;
            }
        }
    }
    return count;
}

图论专题的其他题目

查看图论全部题目 →