力扣286题：墙与门

1.题目描述

��被给定一个 m × n 的二维网格 rooms ，网格中有以下三种可能的初始化值：

1. -1 表示墙或是障碍物
2. 0 表示一扇门
3. INF 无限表示一个空的房间。然后，我们用 231 - 1 = 2147483647 代表 INF。你可以认为通往门的距离总是小于 2147483647 的。

你要给每个空房间位上填上该房间到 最近门的距离 ，如果无法到达门，则填 INF 即可。

示例 1：

输入：rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]输出：[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

示例 2：

输入：rooms = [[-1]]输出：[[-1]]

示例 3：

输入：rooms = [[2147483647]]输出：[[2147483647]]

示例 4：

输入：rooms = [[0]]输出：[[0]]

提示：

• m == rooms.length
• n == rooms[i].length
• 1 {-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //四个方向 // BFS while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i

  我的方法使用了多源广度优先搜索

  3.题目思路与代码讲解

  解答这道题时，第一个遇到的困难便是：

  -我们是从每一个空的房间为源点来进行BFS？之后将每个房间的值替换为当前BFS搜索到一个门所用的次数（即当前房间到最近门的距离）

  -我们是从门出发进行并发BFS？（多源BFS）

  很显然，如果我们从每一个空的房间来进行BFS的话，我们需要进行多次BFS，假设测试用例有10000个空的房间，那就要进行10000次BFS，并且还有很多房间被墙包围，如果进行BFS略显多余，所以这里我们选择后者

  而多源BFS讲究的是将每个源点添加进队列，从而实现并发搜索的目的，所以我们就可以照着这个观念来理解第一部分的代码：

  if (rooms == null || rooms.length == 0 || rooms[0].length == 0) return;//特殊情况判断    int roomsRow = rooms.length, roomsCol = rooms[0].length;Queue queue = new LinkedList(); //存储所有待遍历的元素的队列for (int i = 0; i   
  很显然，代码
   
  if (rooms == null || rooms.length == 0 || rooms[0].length == 0) return;//特殊情况判断
   
  是为了排除无意义的输入（不被力扣出的阴险的测试用例坑到）
   
  int roomsRow = rooms.length, roomsCol = rooms[0].length;
   
  这里我们保存了输入二维矩阵的行&列，方便后续调用
   
  Queue queue = new LinkedList(); //存储所有待遍历的元素的队列
   
  这里我们为之后的BFS创建好了队列，这里使用整型数组当作存储类型，为了存储二维矩阵中的行索引与列索引而准备，所以入队的整型数组大小永远是2
   
  for (int i = 0; i  
  这里我们枚举门的行索引与列索引，题目中说明门的位置值为0，所以我们就检测目标位置值为0的，一旦满足条件就说明找到了一个门，将其添加进队列作为BFS的一个源
   
  int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //四个方向
   
  接下来就是这一串让人匪夷所思的二重数组
   
  在二维矩阵的BFS中，每一个点(x,y)的移动都恒有四种可能性：上，下，左，右，假设不越界，那坐标关系如下：
   
  向上：(x-1,y)，行坐标向上移动一格，纵坐标不变
   
  向下：(x+1,y)，行坐标向下移动一格，纵坐标不变
   
  向左：(x,y-1)，行不变，纵-1
   
  向右：(x,y+1)，行不变，纵+1
   
  这就可以看作是一个四叉树，根节点为(x,y)，分出的四个子节点分别对应着上，下，左，右四种坐标变化，所以我们可以将其存储为一个二维数组，directions[变化方向][0]就是向 变化方向 移动一次的x坐标变化量，同理可得directions[变化方向][1]就是向 变化方向 移动一次的y坐标变化量
   
  当我们要通过已知坐标来获得其向四个方向移动后的坐标，只需要将已知坐标的x与y坐标（这里指行坐标与纵坐标）加上对应在directions数组的变化量即可
    
  接下来就是BFS实现部分
   
  while (!queue.isEmpty()) {    int size = queue.size();    for (int i = 0; i = 0 && newRow = 0 && newCol  
  使用row与col暂存获取到的坐标的横坐标与纵坐标，BFS具体实现大致模板力扣官方已经在《队列与栈》这本Leetbook中讲的很详细了，这里对一些for与while不再做赘述
   
  for (int[] d : directions) {    int newRow = row + d[0], newCol = col + d[1];    if (newRow >= 0 && newRow = 0 && newCol  
  这里是最重要的部分，依次遍历directions里面的四个方向，并且使用row，col中存储的坐标加上变化量组成向四个方向中任一方向移动的新坐标，并且就算不会越界，新坐标的值也可能不是INF（例如移动后坐标是个门或者是墙），所以只接受没有越界并且是空的房间的坐标
   
  rooms[newRow][newCol] = rooms[row][col] + 1;//利用BFS的层次结构
   
  这里利用了BFS的特点，是个人都知道：BFS会对当前层的左右节点进行遍历，假设当前层为d，没有把d层的所有结点遍历完前，是不会打d+1层任何一个结点的主意的。因为门是0，当遍历到门（即根节点）的下一层的节点时，如果有效，就将其加1，那么根节点下一层的房间就是0+1=1，即距离最近的门为1，以此类推
   
  queue.offer(new int[]{newRow, newCol});
   
  之后将这个房间的坐标入队，方便对这个坐标的下一层（即上，下，左，右四个方向进行枚举）进行处理，又因为空房间的值为Integer.MAX_VALUE，而一旦一个坐标被BFS，那他就会被替换为到这个房间最近的门的距离，并且题目担保：
   
  通往门的距离总是小于2147483647
   
  所以根本不用担心会重复搜索
   
  又因为一些房间被墙包围，根本无法到达门，而前面的判断只接受没有越界的空房间，说明被墙包围的房间无论如何都不会被访问到，所以这些房间的值将永远保持Integer.MAX_VALUE，符合题目的说明。
   
  4.复杂度分析
   
  假设矩阵中有n个房间
   
  复杂度为 O(roomsRow * roomsCol + n)
   
  空间复杂度为 O(n)
   
  5.结语
   
  鄙人第一次写文，如有错误请指出，感谢观看！