每日一题 --- 1020. 飞地的数量[力扣][Go]-阿里云开发者社区

每日一题 --- 1020. 飞地的数量[力扣][Go]

2023-02-23 86

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 每日一题 --- 1020. 飞地的数量[力扣][Go]

题目：

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

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

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

解题代码

深度优先搜索

// dirs
// 定义方向
// 右，下，左，上
var dirs = []struct{x,y int}{{-1,0},{1,0},{0,-1},{0,1}}
func numEnclaves(grid [][]int) int {
  m,n := len(grid), len(grid[0])
  // 确定被访问过的陆地
  vis := make([][]bool,m)
  for i := 0; i < m; i++ {
    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 _, dir := range dirs {
      dfs(r+dir.x,c+dir.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)
  }
  // 记录
  ans := 0
  for i := 1; i < m - 1; i++ {
    for j := 1; j < n - 1; j++ {
      if grid[i][j] == 1 && !vis[i][j] {
        ans++
      }
    }
  }
  return ans
}

广度优先搜索

type pair struct{ x, y int }
var dirs = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
func numEnclaves(grid [][]int) int {
  m,n := len(grid), len(grid[0])
  // 确定被访问过的陆地
  vis := make([][]bool,m)
  for i := 0; i < m; i++ {
    vis[i] = make([]bool,n)
  }
  var q []pair
  for i,g:= range grid {
    if g[0] == 1 {
      vis[i][0] = true
      q = append(q,pair{i,0})
    }
    if g[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 _, dir := range dirs {
      if x,y := p.x + dir.x,p.y + dir.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})
      }
    }
  }
  // 记录
  ans := 0
  for i := 1; i < m - 1; i++ {
    for j := 1; j < n - 1; j++ {
      if grid[i][j] == 1 && !vis[i][j] {
        ans++
      }
    }
  }
  return ans
}