This is the 26th day of my participation in the First Challenge 2022

The title

You are given a binary matrix grid of size m x n, where 0 represents an ocean cell and 1 represents a land cell.

A move is a walk from one land cell to another adjacent (up, down, left, right) land cell or across the boundary of the grid.

Returns the number of land cells in the grid that cannot leave the grid boundary in any number of moves.

The sample

Input: the grid = [,0,0,0 [0],,0,1,0 [1], [0,1,1,0], [0,0,0,0]] output: 3: there are three 1 surrounded by 0. A 1 is not surrounded because it's on the boundary.Copy the code

Input: the grid = [,1,1,0 [0], [0,0,1,0], [0,0,1,0], [0,0,0,0]] output: 0 explanation: all 1 or can reach the boundary of the fence.Copy the code

prompt

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 500
  • grid[i][j]The value of0 或 1

Their thinking

The amount of land that cannot reach the boundary of the grid of the island array after any number of moves. So we can just walk across all four of its borders, exclude all the land that’s on the border, and then count the rest of the land that’s surrounded by the ocean to get the final result.

  1. Walk the four sides, find all the critical lands
  2. To exclude the critical land mass
  3. Spread out from the critical point, find all associated land and exclude
  4. Count the land surrounded by the sea

Code implementation

class Solution {
    public int numEnclaves(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        
        // select first and last columns
        for(int x = 0; x < m; ++x){
            if(grid[x][0] = =1){
                dfs(grid, x, 0);
            }

            if(grid[x][n - 1] = =1){
                dfs(grid, x, n - 1); }}// Remove the first and last lines
        for(int y = 0; y < n; ++y){
            if(grid[0][y] == 1){
                dfs(grid, 0, y);
            }

            if(grid[m - 1][y] == 1){
                dfs(grid, m - 1, y); }}// Finally count the landmass
        int count = 0;
        for(int x = 0; x < m; ++x){
            for(int y = 0; y < n; ++y){
                if(grid[x][y] == 1){ ++count; }}}// Return the result
        return count;
    }

    private void dfs(int[][] grid, int x, int y){
        // boundary judgment
        if(x >= grid.length || x < 0 || y >= grid[0].length || y < 0 || grid[x][y] == 0) {return;
        }
        
        // Change the critical land to sea
        grid[x][y] = 0;
        
        // Diffuse around
        dfs(grid, x + 1, y);
        dfs(grid, x - 1, y);
        dfs(grid, x, y + 1);
        dfs(grid, x, y - 1); }}Copy the code