LeetCode 1020. Number of enclaves

1020. The number of enclaves

Give you a size of m x n The binary matrix of grid , among 0 Represents an ocean cell 、1 Represents a land cell .

once Move It refers to walking from one land cell to another （ On 、 Next 、 Left 、 Right ） Land cells or across grid The boundary of the .

Return to grid unable The number of land cells that leave the grid boundary in any number of moves .

Example 1：

 Input ：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
 Output ：3
 explain ： There are three  1  By  0  Surround . One  1  Not surrounded , Because it's on the border .

Example 2：

 Input ：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
 Output ：0
 explain ： all  1  Are on the boundary or can reach the boundary .

Tips ：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 500
• grid[i][j] The value of is 0 or 1

Two 、 Method 1

Depth-first search

class Solution {
    
    int m;
    int n;
    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 res = 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]) {
    
                    res++;
                }
            }
        }
        return res;
    }
    public void dfs(int[][] grid, int x, int y) {
    
        if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y] || grid[x][y] == 0) {
    
            return;
        }
        visited[x][y] = true;
        dfs(grid, x + 1, y);
        dfs(grid, x - 1, y);
        dfs(grid, x, y + 1);
        dfs(grid, x, y - 1);
    }
}

Complexity analysis

• Time complexity ：O(mn), among m and n Grid grid The number of rows and columns . Depth first search accesses each cell at most once , need O(mn) Time for , Traversing the grid to count the number of enclaves also needs O(mn) Time for .

• Spatial complexity ：O(mn), among m and n Grid grid The number of rows and columns . The spatial complexity mainly depends on visited Array and recursive call stack space , The space complexity is O(mn).

3、 ... and 、 Method 2

Breadth first search

class Solution {
    
    public int numEnclaves(int[][] grid) {
    
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        int[][] dirs = {
    {
    1, 0}, {
    -1, 0}, {
    0, 1}, {
    0, -1}};
        for (int i = 0; i < m; i++) {
    
            if (grid[i][0] == 1) {
    
                visited[i][0] = true;
                queue.add(new int[]{
    i, 0});
            }
            if (grid[i][n - 1] == 1) {
    
                visited[i][n - 1] = true;
                queue.add(new int[] {
    i, n - 1});
            }
        }
        for (int j = 1; j < n - 1; j++) {
    
            if (grid[0][j] == 1) {
    
                visited[0][j] = true;
                queue.add(new int[]{
    0, j});
            }
            if (grid[m - 1][j] == 1) {
    
                visited[m - 1][j] = true;
                queue.add(new int[]{
    m - 1, j});
            }
        }
        while(!queue.isEmpty()) {
    
            int[] pos = queue.poll();
            int x = pos[0];
            int y = pos[1];
            for (int[] dir : dirs) {
    
                int row = x + dir[0];
                int col = y + dir[1];
                if (row >= 0 && row < m && col >= 0 && col < n && grid[row][col] == 1 && !visited[row][col]) {
    
                    visited[row][col] = true;
                    queue.add(new int[]{
    row, col});
                }
            }
        }
        int res = 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]) {
    
                    res++;
                }
            }
        }
        return res;
    }
}

Complexity analysis

• Time complexity ：O(mn), among m and n Grid grid The number of rows and columns . Breadth first search accesses each cell at most once , need O(mn) Time for , Traversing the grid to count the number of enclaves also needs O(mn) Time for .

• Spatial complexity ：O(mn), among m and n Grid \grid The number of rows and columns . The spatial complexity mainly depends on visited Array and queue space , The space complexity is O(mn).

Four 、 Method 3

Union checking set

class Solution {
    
    public int numEnclaves(int[][] grid) {
    
        int m = grid.length;
        int n = grid[0].length;
        UnionFind union = 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) {
    
                        union.union(index, index + 1);
                    }
                    if (i + 1 < m && grid[i + 1][j] == 1) {
    
                        union.union(index, index + n);
                    }
                }
            }
        }
        int res = 0;
        for (int i = 1; i < m - 1; i++) {
    
            for (int j = 1; j < n - 1; j++) {
    
                if (grid[i][j] == 1 && !union.isEdge(i * n + j)) {
    
                    res++;
                }
            }
        }
        return res;
    }

    class UnionFind{
    
        int[] p;
        int[] r;
        boolean[] edge;
        public UnionFind(int[][] grid) {
    
            int m = grid.length;
            int n = grid[0].length;
            p = new int[m * n];
            r = new int[m * n];
            edge = new boolean[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;
                        p[index] = index;
                        if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
    
                            edge[index] = true;
                        }
                    }
                }
            }
        }
        public int find(int x) {
    
            if (p[x] != x) {
    
                return find(p[x]);
            }
            return p[x];
        }
        public void union(int x, int y) {
    
            int rootx = find(x);
            int rooty = find(y);
            if (r[rootx] > r[rooty]) {
    
                p[rooty] = rootx;
                edge[rootx] |= edge[rooty];
            } else if (r[rooty] > r[rootx]) {
    
                p[rootx] = rooty;
                edge[rooty] |= edge[rootx];
            } else {
    
                p[rooty] = rootx;
                edge[rootx] |= edge[rooty];
                r[rootx]++;
            }
        }
        public boolean isEdge(int i) {
    
            return edge[find(i)];
        }
    }
}

Complexity analysis

• Time complexity ：O(mn×α(mn)), among m and n Grid grid The number of rows and columns ,α Is the inverse Ackerman function . The join search set here uses path compression and rank merging , The time complexity of a single operation is O(α(mn)), Therefore, the time complexity of the set merging operation of the whole grid is O(mn×α(mn)), After the set search operation, you need O(mn×α(mn)) Time to traverse the grid again and count the number of enclaves , So the total time complexity is O(mn×α(mn)).

• Spatial complexity ：O(mn), among m and n Grid grid The number of rows and columns . And search the set needs O(mn) Space .