LeetCode 1020. 飞地的数量

Categories:

题目描述
思路分析
1. 解法一：边界 BFS（推荐）
相似题目

题目描述

✅ 1020. 飞地的数量

思路分析

解法一：边界 BFS（推荐）

核心思路：

先从边界上的陆地出发进行 BFS/DFS 标记可达陆地。

最终未被标记的陆地即为飞地数量。

只需统计剩余的 1 的数量。

复杂度分析：

时间复杂度：O(mn)，其中 m、n 分别表示网格行列数。

空间复杂度：O(mn)，队列或递归栈使用的空间。

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int numEnclaves(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        Deque<int[]> queue = new ArrayDeque<>();

        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 1) {
                queue.offer(new int[]{i, 0});
            }
            if (grid[i][n - 1] == 1) {
                queue.offer(new int[]{i, n - 1});
            }
        }
        for (int j = 0; j < n; j++) {
            if (grid[0][j] == 1) {
                queue.offer(new int[]{0, j});
            }
            if (grid[m - 1][j] == 1) {
                queue.offer(new int[]{m - 1, j});
            }
        }

        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];

            if (grid[x][y] == 0) {
                continue;
            }

            grid[x][y] = 0;
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                    queue.offer(new int[]{nx, ny});
                }
            }
        }

        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    count++;
                }
            }
        }

        return count;
    }
}

func numEnclaves(grid [][]int) int {
	m := len(grid)
	n := len(grid[0])

	queue := make([][2]int, 0)

	for i := 0; i < m; i++ {
		if grid[i][0] == 1 {
			queue = append(queue, [2]int{i, 0})
		}
		if grid[i][n-1] == 1 {
			queue = append(queue, [2]int{i, n - 1})
		}
	}
	for j := 0; j < n; j++ {
		if grid[0][j] == 1 {
			queue = append(queue, [2]int{0, j})
		}
		if grid[m-1][j] == 1 {
			queue = append(queue, [2]int{m - 1, j})
		}
	}

	dx := []int{1, -1, 0, 0}
	dy := []int{0, 0, 1, -1}

	head := 0
	for head < len(queue) {
		cur := queue[head]
		head++

		x, y := cur[0], cur[1]
		if grid[x][y] == 0 {
			continue
		}
		grid[x][y] = 0

		for k := 0; k < 4; k++ {
			nx := x + dx[k]
			ny := y + dy[k]
			if nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1 {
				queue = append(queue, [2]int{nx, ny})
			}
		}
	}

	count := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				count++
			}
		}
	}

	return count
}

相似题目

题目	难度	考察点
1020. 飞地的数量	中等	BFS/DFS
1254. 统计封闭岛屿的数目	中等	BFS/DFS
695. 岛屿的最大面积	中等	DFS
200. 岛屿数量	中等	BFS/DFS
130. 被围绕的区域	中等	BFS/DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/56612197