每日一题---1034. 边界着色[力扣][Go]-阿里云开发者社区

每日一题---1034. 边界着色[力扣][Go]

2023-02-23 98

版权

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

简介： 每日一题---1034. 边界着色[力扣][Go]

题目描述

给你一个大小为 m x n 的整数矩阵 grid ，表示一个网格。另给你三个整数 row、col 和 color 。网格中的每个值表示该位置处的网格块的颜色。

当两个网格块的颜色相同，而且在四个方向中任意一个方向上相邻时，它们属于同一连通分量。

连通分量的边界是指连通分量中的所有与不在分量中的网格块相邻（四个方向上）的所有网格块，或者在网格的边界上（第一行/列或最后一行/列）的所有网格块。

请你使用指定颜色 color 为所有包含网格块 grid[row][col] 的连通分量的边界进行着色，并返回最终的网格 grid 。

解题代码

深度搜索

// 定义方向
var dirs = []struct{x,y int}{{0,1},{1,0},{-1,0},{0,-1}}
func colorBorder(grid [][]int, row int, col int, color int) [][]int {
  m,n := len(grid),len(grid[0])
  type point struct{ x, y int }
  //borders 用来存边界的横坐标和纵坐标
  borders := []point{}
  //initialColor 用来记录初始颜色
  initialColor := grid[row][col]
  //visit 记录是否被访问过
  visit := make([][]bool,m)
  for i, _ := range visit {
    visit[i] = make([]bool,n)
  }
  //深度搜索函数
  var dfs func(int,int)
  dfs = func(x,y int) {
    visit[x][y] = true
    isBorders := false
    for _, dir := range dirs {
      nx,ny := x+dir.x,y+dir.y
      // 判断边界条件
      if !(nx < m && nx >= 0 && ny < n && ny  >= 0 && grid[nx][ny] == initialColor) {
        isBorders = true
      } else if !visit[nx][ny] {
        visit[nx][ny] = true
        dfs(nx,ny)
      }
    }
    if isBorders {
      borders = append(borders, point{x,y})
    }
  }
  dfs(row, col)
  // 将是边界的点涂上颜色
  for _, border := range borders {
    grid[border.x][border.y] = color
  }
  return grid
}

广度搜索

// 定义方向
var dirs = []struct{x,y int}{{0,1},{1,0},{-1,0},{0,-1}}
func colorBorder(grid [][]int, row int, col int, color int) [][]int {
  m,n := len(grid),len(grid[0])
  type point struct{ x, y int }
  //borders 用来存边界的横坐标和纵坐标
  borders := []point{}
  //initialColor 用来记录初始颜色
  initialColor := grid[row][col]
  //visit 记录是否被访问过
  visit := make([][]bool,m)
  for i, _ := range visit {
    visit[i] = make([]bool,n)
  }
  // 广度搜素，使用队列实现
  q := []point{{row,col}}
  visit[row][col] = true
  for len(q) > 0 {
    p := q[0]
    q = q[1:]
    isBorders := false
    for _, dir := range dirs {
      nx,ny := dir.x + p.x,dir.y + p.y
      if !(nx < m && nx >= 0 && ny < n && ny >=0 && grid[nx][ny] == initialColor) {
        isBorders = true
      } else  if !visit[nx][ny] {
        visit[nx][ny] = true
        q = append(q, point{nx,ny})
      }
    }
    if isBorders {
      borders = append(borders, point{p.x,p.y})
    }
  }
  // 将是边界的点涂上颜色
  for _, border := range borders {
    grid[border.x][border.y] = color
  }
  return grid
}