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.
- Walk the four sides, find all the critical lands
- To exclude the critical land mass
- Spread out from the critical point, find all associated land and exclude
- 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