百度360必应搜狗淘宝本站头条
mqtt服务器xftp6mybatiscollectionkeyerrorc#var
当前位置：网站首页 > 热门文章 > 正文

LeetCode 力扣官方题解 | 1020. 飞地的数量

bigegpt 2024-08-14 14:44 2 浏览

题目描述

给你一个大小为 m x n 的二进制矩阵 grid，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。


示例 1：

输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。

示例 2：

输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：所有 1 都在边界上或可以到达边界。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 500
  • grid[i][j] 的值为 0 或 1


解决方案

方法一：深度优先搜索

思路与算法

根据飞地的定义，如果从一个陆地单元格出发无法移动到网格边界，则这个陆地单元格是飞地。因此可以将所有陆地单元格分成两类：第一类陆地单元格和网格边界相连，这些陆地单元格不是飞地；第二类陆地单元格不和网格边界相连，这些陆地单元格是飞地。

我们可以从网格边界上的每个陆地单元格开始深度优先搜索，遍历完边界之后，所有和网格边界相连的陆地单元格就都被访问过了。然后遍历整个网格，如果网格中的一个陆地单元格没有被访问过，则该陆地单元格不和网格的边界相连，是飞地。

代码实现时，由于网格边界上的单元格一定不是飞地，因此遍历网格统计飞地的数量时只需要遍历不在网格边界上的单元格。


代码

Java

class Solution {
    public static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int m, n;
    private boolean[][] visited;


    public int numEnclaves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            dfs(grid, i, 0);
            dfs(grid, i, n - 1);
        }
        for (int j = 1; j < n - 1; j++) {
            dfs(grid, 0, j);
            dfs(grid, m - 1, j);
        }
        int enclaves = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    enclaves++;
                }
            }
        }
        return enclaves;
    }


    public void dfs(int[][] grid, int row, int col) {
        if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 0 || visited[row][col]) {
            return;
        }
        visited[row][col] = true;
        for (int[] dir : dirs) {
            dfs(grid, row + dir[0], col + dir[1]);
        }
    }
}


C#

public class Solution {
    public static int[][] dirs = {new int[]{-1, 0}, new int[]{1, 0}, new int[]{0, -1}, new int[]{0, 1}};
    private int m, n;
    private bool[][] visited;


    public int NumEnclaves(int[][] grid) {
        m = grid.Length;
        n = grid[0].Length;
        visited = new bool[m][];
        for (int i = 0; i < m; i++) {
            visited[i] = new bool[n];
        }
        for (int i = 0; i < m; i++) {
            DFS(grid, i, 0);
            DFS(grid, i, n - 1);
        }
        for (int j = 1; j < n - 1; j++) {
            DFS(grid, 0, j);
            DFS(grid, m - 1, j);
        }
        int enclaves = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    enclaves++;
                }
            }
        }
        return enclaves;
    }


    public void DFS(int[][] grid, int row, int col) {
        if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 0 || visited[row][col]) {
            return;
        }
        visited[row][col] = true;
        foreach (int[] dir in dirs) {
            DFS(grid, row + dir[0], col + dir[1]);
        }
    }
}


C++

class Solution {
public:
    vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};


    int numEnclaves(vector<vector<int>>& grid) {
        this->m = grid.size();
        this->n = grid[0].size();
        this->visited = vector<vector<bool>>(m, vector<bool>(n, false));
        for (int i = 0; i < m; i++) {
            dfs(grid, i, 0);
            dfs(grid, i, n - 1);
        }
        for (int j = 1; j < n - 1; j++) {
            dfs(grid, 0, j);
            dfs(grid, m - 1, j);
        }
        int enclaves = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    enclaves++;
                }
            }
        }
        return enclaves;
    }


    void dfs(const vector<vector<int>> & grid, int row, int col) {
        if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 0 || visited[row][col]) {
            return;
        }
        visited[row][col] = true;
        for (auto & dir : dirs) {
            dfs(grid, row + dir[0], col + dir[1]);
        }
    }
private:
    int m, n;
    vector<vector<bool>> visited;
};


C

int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};


void dfs(const int** grid, int m, int n, uint8_t** visited, int row, int col) {
    if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 0 || visited[row][col]) {
        return;
    }
    visited[row][col] = 1;
    for (int i = 0; i < 4 ; i++) {
        dfs(grid, m, n, visited, row + dirs[i][0], col + dirs[i][1]);
    }
}


int numEnclaves(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize, n = gridColSize[0];
    uint8_t ** visited = (uint8_t **)malloc(sizeof(uint8_t *) * m);
    for (int i = 0; i < m; i++) {
        visited[i] = (uint8_t *)malloc(sizeof(uint8_t) * n);
        memset(visited[i], 0, sizeof(uint8_t) * n);
    }
    for (int i = 0; i < m; i++) {
        dfs(grid, m, n, visited, i, 0);
        dfs(grid, m, n, visited, i, n - 1);
    }
    for (int j = 1; j < n - 1; j++) {
        dfs(grid, m, n, visited, 0, j);
        dfs(grid, m, n, visited, m - 1, j);
    }
    int enclaves = 0;
    for (int i = 1; i < m - 1; i++) {
        for (int j = 1; j < n - 1; j++) {
            if (grid[i][j] == 1 && !visited[i][j]) {
                enclaves++;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        free(visited[i]);
    }
    free(visited);
    return enclaves;
}

Python3

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        vis = [[False] * n for _ in range(m)]


        def dfs(r: int, c: int) -> None:
            if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == 0 or vis[r][c]:
                return
            vis[r][c] = True
            for x, y in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
                dfs(x, y)


        for i in range(m):
            dfs(i, 0)
            dfs(i, n - 1)
        for j in range(1, n - 1):
            dfs(0, j)
            dfs(m - 1, j)
        return sum(grid[i][j] and not vis[i][j] for i in range(1, m - 1) for j in range(1, n - 1))

Golang

var dirs = []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}


func numEnclaves(grid [][]int) (ans int) {
    m, n := len(grid), len(grid[0])
    vis := make([][]bool, m)
    for i := range vis {
        vis[i] = make([]bool, n)
    }
    var dfs func(int, int)
    dfs = func(r, c int) {
        if r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0 || vis[r][c] {
            return
        }
        vis[r][c] = true
        for _, d := range dirs {
            dfs(r+d.x, c+d.y)
        }
    }
    for i := range grid {
        dfs(i, 0)
        dfs(i, n-1)
    }
    for j := 1; j < n-1; j++ {
        dfs(0, j)
        dfs(m-1, j)
    }
    for i := 1; i < m-1; i++ {
        for j := 1; j < n-1; j++ {
            if grid[i][j] == 1 && !vis[i][j] {
                ans++
            }
        }
    }
    return
}

JavaScript

var numEnclaves = function(grid) {
    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const m = grid.length;
    const n = grid[0].length;
    const visited = new Array(m).fill(0).map(() => new Array(n).fill(false));


    const dfs = (grid, row, col) => {
        if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 0 || visited[row][col]) {
            return;
        }
        visited[row][col] = true;
        for (const dir of dirs) {
            dfs(grid, row + dir[0], col + dir[1]);
        }
    };


    for (let i = 0; i < m; i++) {
        dfs(grid, i, 0);
        dfs(grid, i, n - 1);
    }
    for (let j = 1; j < n - 1; j++) {
        dfs(grid, 0, j);
        dfs(grid, m - 1, j);
    }
    let enclaves = 0;
    for (let i = 1; i < m - 1; i++) {
        for (let j = 1; j < n - 1; j++) {
            if (grid[i][j] === 1 && !visited[i][j]) {
                enclaves++;
            }
        }
    }
    return enclaves;
}

复杂度分析

  • 时间复杂度: O(mn)。其中 m 和 n 分别是网格 grid 的行数和列数。深度优先搜索最多访问每个单元格一次，需要 O(mn) 的时间，遍历网格统计飞地的数量也需要 O(mn) 的时间。
  • 空间复杂度: O(mn) ，其中 m 和 n 分别是网格 grid 的行数和列数。空间复杂度主要取决于 visited 数组和递归调用栈空间，空间复杂度是 O(mn)。

方法二：广度优先搜索

也可以通过广度优先搜索判断每个陆地单元格是否和网格边界相连。

首先从网格边界上的每个陆地单元格开始广度优先搜索，访问所有和网格边界相连的陆地单元格，然后遍历整个网格，统计飞地的数量。


代码

Java

class Solution {
    public static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};


    public int numEnclaves(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new ArrayDeque<int[]>();
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 1) {
                visited[i][0] = true;
                queue.offer(new int[]{i, 0});
            }
            if (grid[i][n - 1] == 1) {
                visited[i][n - 1] = true;
                queue.offer(new int[]{i, n - 1});
            }
        }
        for (int j = 1; j < n - 1; j++) {
            if (grid[0][j] == 1) {
                visited[0][j] = true;
                queue.offer(new int[]{0, j});
            }
            if (grid[m - 1][j] == 1) {
                visited[m - 1][j] = true;
                queue.offer(new int[]{m - 1, j});
            }
        }
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int currRow = cell[0], currCol = cell[1];
            for (int[] dir : dirs) {
                int nextRow = currRow + dir[0], nextCol = currCol + dir[1];
                if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && grid[nextRow][nextCol] == 1 && !visited[nextRow][nextCol]) {
                    visited[nextRow][nextCol] = true;
                    queue.offer(new int[]{nextRow, nextCol});
                }
            }
        }
        int enclaves = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    enclaves++;
                }
            }
        }
        return enclaves;
    }
}

C#

public class Solution {
    public static int[][] dirs = {new int[]{-1, 0}, new int[]{1, 0}, new int[]{0, -1}, new int[]{0, 1}};


    public int NumEnclaves(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        bool[][] visited = new bool[m][];
        for (int i = 0; i < m; i++) {
            visited[i] = new bool[n];
        }
        Queue<Tuple<int, int>> queue = new Queue<Tuple<int, int>>();
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 1) {
                visited[i][0] = true;
                queue.Enqueue(new Tuple<int, int>(i, 0));
            }
            if (grid[i][n - 1] == 1) {
                visited[i][n - 1] = true;
                queue.Enqueue(new Tuple<int, int>(i, n - 1));
            }
        }
        for (int j = 1; j < n - 1; j++) {
            if (grid[0][j] == 1) {
                visited[0][j] = true;
                queue.Enqueue(new Tuple<int, int>(0, j));
            }
            if (grid[m - 1][j] == 1) {
                visited[m - 1][j] = true;
                queue.Enqueue(new Tuple<int, int>(m - 1, j));
            }
        }
        while (queue.Count > 0) {
            Tuple<int, int> cell = queue.Dequeue();
            int currRow = cell.Item1, currCol = cell.Item2;
            foreach (int[] dir in dirs) {
                int nextRow = currRow + dir[0], nextCol = currCol + dir[1];
                if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && grid[nextRow][nextCol] == 1 && !visited[nextRow][nextCol]) {
                    visited[nextRow][nextCol] = true;
                    queue.Enqueue(new Tuple<int, int>(nextRow, nextCol));
                }
            }
        }
        int enclaves = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    enclaves++;
                }
            }
        }
        return enclaves;
    }
}

C++

class Solution {
public:
    vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};


    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> visited = vector<vector<bool>>(m, vector<bool>(n, false));
        queue<pair<int,int>> qu;
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 1) {
                visited[i][0] = true;
                qu.emplace(i, 0);
            }
            if (grid[i][n - 1] == 1) {
                visited[i][n - 1] = true;
                qu.emplace(i, n - 1);
            }
        }
        for (int j = 1; j < n - 1; j++) {
            if (grid[0][j] == 1) {
                visited[0][j] = true;
                qu.emplace(0, j);
            }
            if (grid[m - 1][j] == 1) {
                visited[m - 1][j] = true;
                qu.emplace(m - 1, j);
            }
        }
        while (!qu.empty()) {
            auto [currRow, currCol] = qu.front();
            qu.pop();
            for (auto & dir : dirs) {
                int nextRow = currRow + dir[0], nextCol = currCol + dir[1];
                if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && grid[nextRow][nextCol] == 1 && !visited[nextRow][nextCol]) {
                    visited[nextRow][nextCol] = true;
                    qu.emplace(nextRow, nextCol);
                }
            }
        }
        int enclaves = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    enclaves++;
                }
            }
        }
        return enclaves;
    }
};

C

typedef struct {
    int x;
    int y;
} Pair;


int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};


int numEnclaves(int** grid, int gridSize, int* gridColSize){
    int m = gridSize, n = gridColSize[0];
    bool ** visited = (bool **)malloc(sizeof(bool *) * m);
    for (int i = 0; i < m; i++) {
        visited[i] = (bool *)malloc(sizeof(bool) * n);
        memset(visited[i], 0, sizeof(bool) * n);
    }
    Pair * queue = (Pair *)malloc(sizeof(Pair) * m * n);
    int head = 0;
    int tail = 0;
    for (int i = 0; i < m; i++) {
        if (grid[i][0] == 1) {
            visited[i][0] = true;
            queue[tail].x = i;
            queue[tail].y = 0;
            tail++;
        }
        if (grid[i][n - 1] == 1) {
            visited[i][n - 1] = true;
            queue[tail].x = i;
            queue[tail].y = n - 1;
            tail++;
        }
    }
    for (int j = 1; j < n - 1; j++) {
        if (grid[0][j] == 1) {
            visited[0][j] = true;
            queue[tail].x = 0;
            queue[tail].y = j;
            tail++;
        }
        if (grid[m - 1][j] == 1) {
            visited[m - 1][j] = true;
            queue[tail].x = m - 1;
            queue[tail].y = j;
            tail++;
        }
    }
    while (head != tail) {
        int currRow = queue[head].x;
        int currCol = queue[head].y;
        head++;
        for (int i = 0; i < 4; i++) {
            int nextRow = currRow + dirs[i][0], nextCol = currCol + dirs[i][1];
            if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && grid[nextRow][nextCol] == 1 && !visited[nextRow][nextCol]) {
                visited[nextRow][nextCol] = true;
                queue[tail].x = nextRow;
                queue[tail].y = nextCol;
                tail++;
            }
        }
    }
    int enclaves = 0;
    for (int i = 1; i < m - 1; i++) {
        for (int j = 1; j < n - 1; j++) {
            if (grid[i][j] == 1 && !visited[i][j]) {
                enclaves++;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        free(visited[i]);
    }
    free(visited);
    free(queue);
    return enclaves;
}

Python3

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        vis = [[False] * n for _ in range(m)]
        q = deque()
        for i, row in enumerate(grid):
            if row[0]:
                vis[i][0] = True
                q.append((i, 0))
            if row[n - 1]:
                vis[i][n - 1] = True
                q.append((i, n - 1))
        for j in range(1, n - 1):
            if grid[0][j]:
                vis[0][j] = True
                q.append((0, j))
            if grid[m - 1][j]:
                vis[m - 1][j] = True
                q.append((m - 1, j))
        while q:
            r, c = q.popleft()
            for x, y in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
                if 0 <= x < m and 0 <= y < n and grid[x][y] and not vis[x][y]:
                    vis[x][y] = True
                    q.append((x, y))
        return sum(grid[i][j] and not vis[i][j] for i in range(1, m - 1) for j in range(1, n - 1))

Golang

type pair struct{ x, y int }
var dirs = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}


func numEnclaves(grid [][]int) (ans int) {
    m, n := len(grid), len(grid[0])
    vis := make([][]bool, m)
    for i := range vis {
        vis[i] = make([]bool, n)
    }
    q := []pair{}
    for i, row := range grid {
        if row[0] == 1 {
            vis[i][0] = true
            q = append(q, pair{i, 0})
        }
        if row[n-1] == 1 {
            vis[i][n-1] = true
            q = append(q, pair{i, n - 1})
        }
    }
    for j := 1; j < n-1; j++ {
        if grid[0][j] == 1 {
            vis[0][j] = true
            q = append(q, pair{0, j})
        }
        if grid[m-1][j] == 1 {
            vis[m-1][j] = true
            q = append(q, pair{m - 1, j})
        }
    }
    for len(q) > 0 {
        p := q[0]
        q = q[1:]
        for _, d := range dirs {
            if x, y := p.x+d.x, p.y+d.y; 0 <= x && x < m && 0 <= y && y < n && grid[x][y] == 1 && !vis[x][y] {
                vis[x][y] = true
                q = append(q, pair{x, y})
            }
        }
    }
    for i := 1; i < m-1; i++ {
        for j := 1; j < n-1; j++ {
            if grid[i][j] == 1 && !vis[i][j] {
                ans++
            }
        }
    }
    return
}

JavaScript

var numEnclaves = function(grid) {
    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const m = grid.length, n = grid[0].length;
    const visited = new Array(m).fill(0).map(() => new Array(n).fill(false));
    const queue = [];
    for (let i = 0; i < m; i++) {
        if (grid[i][0] === 1) {
            visited[i][0] = true;
            queue.push([i, 0]);
        }
        if (grid[i][n - 1] === 1) {
            visited[i][n - 1] = true;
            queue.push([i, n - 1]);
        }
    }
    for (let j = 1; j < n - 1; j++) {
        if (grid[0][j] === 1) {
            visited[0][j] = true;
            queue.push([0, j]);
        }
        if (grid[m - 1][j] === 1) {
            visited[m - 1][j] = true;
            queue.push([m - 1, j]);
        }
    }
    while (queue.length) {
        const cell = queue.shift();
        const currRow = cell[0], currCol = cell[1];
        for (const dir of dirs) {
            const nextRow = currRow + dir[0], nextCol = currCol + dir[1];
            if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && grid[nextRow][nextCol] == 1 && !visited[nextRow][nextCol]) {
                visited[nextRow][nextCol] = true;
                queue.push([nextRow, nextCol]);
            }
        }
    }
    let enclaves = 0;
    for (let i = 1; i < m - 1; i++) {
        for (let j = 1; j < n - 1; j++) {
            if (grid[i][j] === 1 && !visited[i][j]) {
                enclaves++;
            }
        }
    }
    return enclaves;
};

复杂度分析

  • 时间复杂度: O(mn)。其中 m 和 n 分别是网格 grid 的行数和列数。广度优先搜索最多访问每个单元格一次，需要 O(mn) 的时间，遍历网格统计飞地的数量也需要 O(mn) 的时间。
  • 空间复杂度: O(mn) ，其中 m 和 n 分别是网格 grid 的行数和列数。空间复杂度主要取决于 visited 数组和队列空间，空间复杂度是 O(mn)。

方法三：并查集

除了深度优先搜索和广度优先搜索的方法以外，也可以使用并查集判断每个陆地单元格是否和网格边界相连。

并查集的核心思想是计算网格中的每个陆地单元格所在的连通分量。对于网格边界上的每个陆地单元格，其所在的连通分量中的所有陆地单元格都不是飞地。如果一个陆地单元格所在的连通分量不同于任何一个网格边界上的陆地单元格所在的连通分量，则该陆地单元格是飞地。

并查集的做法是，遍历整个网格，对于网格中的每个陆地单元格，将其与所有相邻的陆地单元格做合并操作。由于需要判断每个陆地单元格所在的连通分量是否和网格边界相连，因此并查集还需要记录每个单元格是否和网格边界相连的信息，在合并操作时更新该信息。

在遍历网格完成并查集的合并操作之后，再次遍历整个网格，通过并查集中的信息判断每个陆地单元格是否和网格边界相连，统计飞地的数量。


代码

Java

class Solution {
    public int numEnclaves(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        UnionFind uf = new UnionFind(grid);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int index = i * n + j;
                    if (j + 1 < n && grid[i][j + 1] == 1) {
                        uf.union(index, index + 1);
                    }
                    if (i + 1 < m && grid[i + 1][j] == 1) {
                        uf.union(index, index + n);
                    }
                }
            }
        }
        int enclaves = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 1 && !uf.isOnEdge(i * n + j)) {
                    enclaves++;
                }
            }
        }
        return enclaves;
    }
}


class UnionFind {
    private int[] parent;
    private boolean[] onEdge;
    private int[] rank;


    public UnionFind(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        parent = new int[m * n];
        onEdge = new boolean[m * n];
        rank = new int[m * n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int index = i * n + j;
                    parent[index] = index;
                    if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                        onEdge[index] = true;
                    }
                }
            }
        }
    }


    public int find(int i) {
        if (parent[i] != i) {
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }


    public void union(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            if (rank[rootx] > rank[rooty]) {
                parent[rooty] = rootx;
                onEdge[rootx] |= onEdge[rooty];
            } else if (rank[rootx] < rank[rooty]) {
                parent[rootx] = rooty;
                onEdge[rooty] |= onEdge[rootx];
            } else {
                parent[rooty] = rootx;
                onEdge[rootx] |= onEdge[rooty];
                rank[rootx]++;
            }
        }
    }


    public boolean isOnEdge(int i) {
        return onEdge[find(i)];
    }
}

C#

public class Solution {
    public int NumEnclaves(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        UnionFind uf = new UnionFind(grid);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int index = i * n + j;
                    if (j + 1 < n && grid[i][j + 1] == 1) {
                        uf.Union(index, index + 1);
                    }
                    if (i + 1 < m && grid[i + 1][j] == 1) {
                        uf.Union(index, index + n);
                    }
                }
            }
        }
        int enclaves = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 1 && !uf.IsOnEdge(i * n + j)) {
                    enclaves++;
                }
            }
        }
        return enclaves;
    }
}


class UnionFind {
    private int[] parent;
    private bool[] onEdge;
    private int[] rank;


    public UnionFind(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        parent = new int[m * n];
        onEdge = new bool[m * n];
        rank = new int[m * n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int index = i * n + j;
                    parent[index] = index;
                    if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                        onEdge[index] = true;
                    }
                }
            }
        }
    }


    public int Find(int i) {
        if (parent[i] != i) {
            parent[i] = Find(parent[i]);
        }
        return parent[i];
    }


    public void Union(int x, int y) {
        int rootx = Find(x);
        int rooty = Find(y);
        if (rootx != rooty) {
            if (rank[rootx] > rank[rooty]) {
                parent[rooty] = rootx;
                onEdge[rootx] |= onEdge[rooty];
            } else if (rank[rootx] < rank[rooty]) {
                parent[rootx] = rooty;
                onEdge[rooty] |= onEdge[rootx];
            } else {
                parent[rooty] = rootx;
                onEdge[rootx] |= onEdge[rooty];
                rank[rootx]++;
            }
        }
    }


    public bool IsOnEdge(int i) {
        return onEdge[Find(i)];
    }
}

C++

class UnionFind {
public:
    UnionFind(const vector<vector<int>> & grid) {
        int m = grid.size(), n = grid[0].size();
        this->parent = vector<int>(m * n);
        this->onEdge = vector<bool>(m * n, false);
        this->rank = vector<int>(m * n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int index = i * n + j;
                    parent[index] = index;
                    if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                        onEdge[index] = true;
                    }
                }
            }
        }
    }


    int find(int i) {
        if (parent[i] != i) {
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }


    void uni(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            if (rank[rootx] > rank[rooty]) {
                parent[rooty] = rootx;
                onEdge[rootx] = onEdge[rootx] | onEdge[rooty];
            } else if (rank[rootx] < rank[rooty]) {
                parent[rootx] = rooty;
                onEdge[rooty] = onEdge[rooty] | onEdge[rootx];
            } else {
                parent[rooty] = rootx;
                onEdge[rootx] = onEdge[rootx] | onEdge[rooty];
                rank[rootx]++;
            }
        }
    }


    bool isOnEdge(int i) {
        return onEdge[find(i)];
    }
private:
    vector<int> parent;
    vector<bool> onEdge;
    vector<int> rank;    
};


class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        UnionFind uf(grid);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int index = i * n + j;
                    if (j + 1 < n && grid[i][j + 1] == 1) {
                        uf.uni(index, index + 1);
                    }
                    if (i + 1 < m && grid[i + 1][j] == 1) {
                        uf.uni(index, index + n);
                    }
                }
            }
        }
        int enclaves = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 1 && !uf.isOnEdge(i * n + j)) {
                    enclaves++;
                }
            }
        }
        return enclaves;
    }
};

C

typedef struct {
    int * parent;
    bool * onEdge;
    int * rank;  
} UnionFind;


void initUnionFind(UnionFind * uf, const int** grid, int gridSize, int* gridColSize) {
    int m = gridSize, n = gridColSize[0];
    assert(NULL != uf);
    uf->parent = (int *)malloc(sizeof(int) * m * n);
    uf->onEdge = (bool *)malloc(sizeof(bool) * m * n);
    uf->rank = (int *)malloc(sizeof(int) * m * n);
    memset(uf->parent, 0, sizeof(int) * m * n);
    memset(uf->onEdge, 0, sizeof(bool) * m * n);
    memset(uf->rank, 0, sizeof(int) * m * n);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                int index = i * n + j;
                uf->parent[index] = index;
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    uf->onEdge[index] = true;
                }
            }
        }
    }
}


void freeUnionFind(UnionFind * uf) {
    free(uf->parent);
    free(uf->onEdge);
    free(uf->rank);
}


int find(UnionFind * uf, int i) {
    if (uf->parent[i] != i) {
        uf->parent[i] = find(uf, uf->parent[i]);
    }
    return uf->parent[i];
}


void uni(UnionFind * uf, int x, int y) {
    int rootx = find(uf, x);
    int rooty = find(uf, y);
    if (rootx != rooty) {
        if (uf->rank[rootx] > uf->rank[rooty]) {
            uf->parent[rooty] = rootx;
            uf->onEdge[rootx] = uf->onEdge[rootx] | uf->onEdge[rooty];
        } else if (uf->rank[rootx] < uf->rank[rooty]) {
            uf->parent[rootx] = rooty;
            uf->onEdge[rooty] = uf->onEdge[rooty] | uf->onEdge[rootx];
        } else {
            uf->parent[rooty] = rootx;
            uf->onEdge[rootx] = uf->onEdge[rootx] | uf->onEdge[rooty];
            uf->rank[rootx]++;
        }
    }
}


bool isOnEdge(UnionFind * uf, int i) {
    return uf->onEdge[find(uf, i)];
}


int numEnclaves(int** grid, int gridSize, int* gridColSize){
    int m = gridSize, n = gridColSize[0];
    UnionFind * uf = (UnionFind *)malloc(sizeof(UnionFind));
    initUnionFind(uf, grid, gridSize, gridColSize);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                int index = i * n + j;
                if (j + 1 < n && grid[i][j + 1] == 1) {
                    uni(uf, index, index + 1);
                }
                if (i + 1 < m && grid[i + 1][j] == 1) {
                    uni(uf, index, index + n);
                }
            }
        }
    }
    int enclaves = 0;
    for (int i = 1; i < m - 1; i++) {
        for (int j = 1; j < n - 1; j++) {
            if (grid[i][j] == 1 && !isOnEdge(uf, i * n + j)) {
                enclaves++;
            }
        }
    }
    freeUnionFind(uf);
    free(uf);
    return enclaves;
}

Python3

class UnionFind:
    def __init__(self, grid: List[List[int]]):
        m, n = len(grid), len(grid[0])
        self.parent = [0] * (m * n)
        self.rank = [0] * (m * n)
        self.onEdge = [False] * (m * n)
        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                if v:
                    idx = i * n + j
                    self.parent[idx] = idx
                    if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                        self.onEdge[idx] = True


    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]


    def merge(self, x: int, y: int) -> None:
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.parent[y] = x
            self.onEdge[x] |= self.onEdge[y]
        elif self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.onEdge[y] |= self.onEdge[x]
        else:
            self.parent[y] = x
            self.onEdge[x] |= self.onEdge[y]
            self.rank[x] += 1


class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        uf = UnionFind(grid)
        m, n = len(grid), len(grid[0])
        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                if v:
                    idx = i * n + j
                    if j + 1 < n and grid[i][j + 1]:
                        uf.merge(idx, idx + 1)
                    if i + 1 < m and grid[i + 1][j]:
                        uf.merge(idx, idx + n)
        return sum(grid[i][j] and not uf.onEdge[uf.find(i * n + j)] for i in range(1, m - 1) for j in range(1, n - 1))

Golang

type unionFind struct {
    parent []int
    rank   []int
    onEdge []bool
}


func newUnionFind(grid [][]int) unionFind {
    m, n := len(grid), len(grid[0])
    parent := make([]int, m*n)
    rank := make([]int, m*n)
    onEdge := make([]bool, m*n)
    for i, row := range grid {
        for j, v := range row {
            if v == 1 {
                idx := i*n + j
                parent[idx] = idx
                if i == 0 || i == m-1 || j == 0 || j == n-1 {
                    onEdge[idx] = true
                }
            }
        }
    }
    return unionFind{parent, rank, onEdge}
}


func (uf unionFind) find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.find(uf.parent[x])
    }
    return uf.parent[x]
}


func (uf unionFind) merge(x, y int) {
    x, y = uf.find(x), uf.find(y)
    if x == y {
        return
    }
    if uf.rank[x] > uf.rank[y] {
        uf.parent[y] = x
        uf.onEdge[x] = uf.onEdge[x] || uf.onEdge[y]
    } else if uf.rank[x] < uf.rank[y] {
        uf.parent[x] = y
        uf.onEdge[y] = uf.onEdge[y] || uf.onEdge[x]
    } else {
        uf.parent[y] = x
        uf.onEdge[x] = uf.onEdge[x] || uf.onEdge[y]
        uf.rank[x]++
    }
}


func numEnclaves(grid [][]int) (ans int) {
    uf := newUnionFind(grid)
    m, n := len(grid), len(grid[0])
    for i, row := range grid {
        for j, v := range row {
            if v == 1 {
                idx := i*n + j
                if j+1 < n && grid[i][j+1] == 1 {
                    uf.merge(idx, idx+1)
                }
                if i+1 < m && grid[i+1][j] == 1 {
                    uf.merge(idx, idx+n)
                }
            }
        }
    }
    for i := 1; i < m-1; i++ {
        for j := 1; j < n-1; j++ {
            if grid[i][j] == 1 && !uf.onEdge[uf.find(i*n+j)] {
                ans++
            }
        }
    }
    return
}

JavaScript

var numEnclaves = function(grid) {
    const m = grid.length, n = grid[0].length;
    const uf = new UnionFind(grid);
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                const index = i * n + j;
                if (j + 1 < n && grid[i][j + 1] === 1) {
                    uf.union(index, index + 1);
                }
                if (i + 1 < m && grid[i + 1][j] === 1) {
                    uf.union(index, index + n);
                }
            }
        }
    }
    let enclaves = 0;
    for (let i = 1; i < m - 1; i++) {
        for (let j = 1; j < n - 1; j++) {
            if (grid[i][j] === 1 && !uf.isOnEdge(i * n + j)) {
                enclaves++;
            }
        }
    }
    return enclaves;
}


class UnionFind {
    constructor(grid) {
        const m = grid.length, n = grid[0].length;
        this.parent = new Array(m * n).fill(0);
        this.onEdge = new Array(m * n).fill(false);
        this.rank = new Array(m * n).fill(0);
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (grid[i][j] === 1) {
                    const index = i * n + j;
                    this.parent[index] = index;
                    if (i === 0 || i === m - 1 || j === 0 || j === n - 1) {
                        this.onEdge[index] = true;
                    }
                }
            }
        }
    }


    find(i) {
        if (this.parent[i] !== i) {
            this.parent[i] = this.find(this.parent[i]);
        }
        return this.parent[i];
    }


    union(x, y) {
        const rootx = this.find(x);
        const rooty = this.find(y);
        if (rootx !== rooty) {
            if (this.rank[rootx] > this.rank[rooty]) {
                this.parent[rooty] = rootx;
                this.onEdge[rootx] |= this.onEdge[rooty];
            } else if (this.rank[rootx] < this.rank[rooty]) {
                this.parent[rootx] = rooty;
                this.onEdge[rooty] |= this.onEdge[rootx];
            } else {
                this.parent[rooty] = rootx;
                this.onEdge[rootx] |= this.onEdge[rooty];
                this.rank[rootx]++;
            }
        }
    }


    isOnEdge(i) {
        return this.onEdge[this.find(i)];
    }
}

复杂度分析

  • 时间复杂度: O(mn X α(mn))，其中 m 和 n 分别是网格 grid 的行数和列数。α 是反阿克曼函数。这里的并查集使用了路径压缩和按秩合并，单次操作的时间复杂度是 O(α(mn))，因此整个网格的并查集操作的时间复杂度是 O(mn X α(mn))，并查集操作之后需要 O(mn X α(mn)) 的时间再次遍历网格统计飞地的数量，因此总时间复杂度是 O(mn X α(mn)) 。

  • 空间复杂度: O(mn) ，其中 m 和 n 分别是网格 grid 的行数和列数。并查集需要 O(mn) 的空间。


BY /

本文作者：力扣

声明：本文归“力扣”版权所有，如需转载请联系。

相关推荐

为3D手游打造， Visual Studio Unity扩展下载

IT之家（www.ithome.com）：为3D手游打造，VisualStudioUnity扩展下载7月30日消息，微软正式发布升级版VisualStudioToolsforUnity扩...

由ArcMap属性字段自增引出字段计算器使用Python的技巧

1.前言前些日子有人问我ArcMap中要让某个字段的值实现自增有什么方法？我首先想到像SQLServer中对于数值型字段可以设置自增。所以我打开ArcCatalog查看发现只提供默认值，没办法只能看...

微软首次回答 HoloLens 相关问题，终于爆料了

fengo2015/04/2115:11注：本文作者张静是NVIDIAGPU架构师，微信公众号“黑客与画家”（HackerAndPainter），知乎专栏地址。欢迎各位童鞋与他交流探讨。...

C#指针的应用（c#指针类型）

C#在有限的范围内支持指针。C#的指针只不过是一个持有另一类型内存地址的变量。但是在C#中，指针只能被声明为持有值类型和数组的内存地址。与引用类型不同，指针类型不被默认的垃圾收集机制所跟踪。出于同...

C# 堆栈(Stack)（c# 堆栈中定位调用messagebox 的地方）

C#集合在C#中，堆栈（Stack）是一种后进先出（LIFO,LastInFirstOut）的数据结构。堆栈（Stack）适用于存储和按顺序处理数据，其中最新添加的元素会最先被移除。堆...

欢迎回来:Fortran意外重回流行编程语言20强榜单

TIOBE指数是用来确定一种编程语言受欢迎程度的指标之一。它并不表明哪种编程语言是最好的，也不表明哪种编程语言写的代码行数最多，而是利用在谷歌、维基百科、必应、亚马逊、YouTube等各种引擎和网站上...

C#+NET MAUI实现跨平台/终端(linux,win,ios等)解决方案

简介.NETMulti-platformAppUI(.NETMAUI)是一个跨平台的框架，用于使用C#和XAML创建移动和桌面应用程序。使用.NETMAUI，您可以用一套代码库开发可以在A...

C#代码安全红线:SQL注入防护终极方案，让你的系统固若金汤

在数字化时代，应用系统的安全性至关重要。而SQL注入攻击，长期盘踞在OWASP（OpenWebApplicationSecurityProject）漏洞榜单的前列，成为众多基于数据库的应用系统...

C# (一)状态机模式（状态机代码实现）

最近空闲，炒炒隔夜饭，以前这些模式在自己项目种应用过不少，但一直没有像别人那样写一个系列，最近年纪大了，很多东西都忘记了，特别AI的兴起，更少写代码了，反正没什么事情，自己在重写一遍吧。创建型模式（5...

C# 中 Predicate 详解（c#中的replace）

Predicate泛型委托：表示定义一组条件并确定指定对象是否符合这些条件的方法。此委托由Array和List类的几种方法使用，用于在集合中搜索元素。Predicate<T>...

C#中$的用法?（c#中&&什么意思）

文章来自AI问答。在C#中，$符号用于字符串插值（StringInterpolation）。字符串插值是C#6.0引入的一种特性，它允许你在字符串中直接嵌入表达式，而不需要使用string.For...

C#并行编程:Parallel类（c# 并行处理）

在Parallel类中提供了三个静态方法作为结构化并行的基本形式：Parallel.Invoke方法：并行执行一组委托。Parallel.For方法：执行与C#for循环等价的并行方法。Parall...

颠覆认知!用Span重构foreach循环竟让数据处理快如闪电

在C#编程的世界里，数据处理效率始终是开发者们关注的焦点。随着项目规模的扩大和数据量的激增，哪怕是细微的性能提升，都可能对整个应用的响应速度和用户体验产生深远影响。近年来，C#引入的Span<T...

Unity3D手游开发实践《腾讯桌球》客户端开发经验总结

本次分享总结，起源于腾讯桌球项目，但是不仅仅限于项目本身。虽然基于Unity3D，很多东西同样适用于Cocos。本文从以下10大点进行阐述：1.架构设计2.原生插件/平台交互3.版本与补丁4.用脚本，...

.NET 7 AOT 的使用以及 .NET 与 Go 互相调用

目录背景C#部分环境要求创建一个控制台项目体验AOT编译C#调用库函数减少体积C#导出函数C#调用C#生成的AOTGolang部分安装GCCGolang导出函数.NETC#...

一周热门
最近发表
标签列表