LeetCode75学习计划-图的DFS/BFS

算法解题思路很多会借鉴于题解区，如果侵权请联系删除。

本章节知识点为图的DFS/BFS。

钥匙和房间

题目标签：

• 图
• 深度优先搜索
• 广度优先搜索

题目难度： Medium

题目描述：

有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。

当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。

给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。

解题思路：

• 深度优先访问房间，对访问过的房间进行标记，最后判断是否能访问所有房间

代码实现：

func canVisitAllRooms(rooms [][]int) bool {
  n := len(rooms)
  // 记录每个房间是否被访问了
  visit := make([]bool, n)
  // 记录已经访问的房间的数量
  num := 0
  
  // dfs算法
  var dfs func([][]int, int)
  dfs = func(s [][]int, x int) {
    // 将要访问的房间标记为已访问
    visit[x] = true
    // 更新已访问的数量
    num ++
    for _, room := range s[x] {
      // 遍历从当前房间能够去往的房间，如果没去过就去
      if !visit[room] {
        dfs(s, room)
      }
    }
  }

  // 运行dfs算法计算能访问多少房间，如果能访问的房间数与房间总数一致则能全部访问
  dfs(rooms, 0)
  return num == n
}

省份数量

题目标签：

• 图
• 深度优先搜索
• 广度优先搜索

题目难度： Medium

题目描述：

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

解题思路：

• 与上题类似，dfs加标记节点

代码实现：

func findCircleNum(isConnected [][]int) int {
  res := 0
  // 标记是否是省份
  visit := make([]bool, len(isConnected))
  var dfs func(int)
  dfs = func(from int) {
    visit[from] = true
    for to, conn := range isConnected[from] {
      // 如果conn=1则可以到达该省份
      // 如果还没有从该省份出发，则从该省份出发计算
      if conn == 1 && !visit[to] {
        dfs(to)
      }
    }
  }
  for i, v := range visit {
    if !v {
      res ++
      dfs(i)
    }
  }
  return res
}

迷宫中离入口最近的出口

题目标签：

• 数组
• 矩阵
• 广度优先搜索

题目难度： Medium

题目描述：

给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。

每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。

请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。

解题思路：

• 从起点开始，广度遍历找出口，最近的一个出口返回

代码实现：

func nearestExit(maze [][]byte, entrance []int) int {
  // 行
  m := len(maze) 
  // 列
  n := len(maze[0])
  // 上下左右四个相邻坐标对应的行列变化量
  dx := []int{1, 0, -1, 0}
  dy := []int{0, 1, 0, -1}
  // 队列
  queue := [][]int{}
  // 入口加入到队列并修改为墙
  queue = append(queue, []int{entrance[0], entrance[1], 0})
  maze[entrance[0]][entrance[1]] = '+'
  for len(queue) > 0 {
    // 队列的第一个元素，就是队列中离起点最近的元素
    temp := queue[:1]
    queue = queue[1:]
    // 元素的位置和距离开始节点的距离
    cx, cy, d := temp[0][0], temp[0][1], temp[0][2]
    // 遍历四个方向的点
    for i := 0; i < 4; i++ {
      nx := cx + dx[i]
      ny := cy + dy[i]
      // 合法且不是墙
      if 0 <= nx && nx < m && 0 <= ny && ny < n && maze[nx][ny] == '.' {
        // 找到出口了
        if nx == 0 || nx == m - 1 || ny == 0 || ny == n-1 {
          return d + 1
        }
        // 没找到出口，当前点设置为墙，继续找
        maze[nx][ny] = '+'
        queue = append(queue, []int{nx, ny, d+1})
      }
    }
  }
  return -1
}

腐烂的橘子

题目标签：

• 数组
• 矩阵
• 广度优先搜索

题目难度： Medium

题目描述：

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

解题思路：

• 与上题类似，还是一层层遍历即可

代码实现：

func orangesRotting(grid [][]int) int {
  // 行列
  m := len(grid)
  n := len(grid[0])
  // 新鲜橘子的数量
  fresh := m * n
  // 队列
  queue := [][]int{}
  // 找出初始的腐烂橘子加入队列
  for i, valX := range grid {
    for j, valY := range valX {
      // 如果是腐烂的加入到队列中,并减少新鲜橘子的数量
      if valY == 2 {
        queue = append(queue, []int{i, j, 0})
        fresh -= 1
      // 空格子减少新鲜橘子的数量
      } else if valY == 0 {
	    fresh -= 1
      }
    }
  }
  // 上下左右四个相邻坐标对应的行列变化量
  dx := []int{1, 0, -1, 0}
  dy := []int{0, 1, 0, -1}


  // 全部腐烂需要的时间，bfs每执行一次需要1分钟，最后一层执行完就是时间
  d := 0
  for len(queue) > 0 {
    temp := queue[:1]
    queue = queue[1:]
    x := temp[0][0]
    y := temp[0][1]
    d = temp[0][2]
    // 遍历四个方向的点
    for i := 0; i < 4; i++ {
      nx := x + dx[i]
      ny := y + dy[i]
      // 还是新鲜的橘子
      if 0 <= nx && nx < m && 0 <= ny && ny < n && grid[nx][ny] == 1 {
        grid[nx][ny] = 2
        queue = append(queue, []int{nx, ny, d+1})
        fresh -= 1
      }
    }
  }
  if fresh > 0 {
    return -1
  }
  return d
}