单源点系列:
一、二进制矩阵中的最短路径
给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。
二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：
- 路径途经的所有单元格的值都是
0。 - 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
思路：
由题意可得，bfs是从(0,0)出发(单源点)，然后找到一条最短畅通路径的长度。
1.首先我们要判断起点和终点的值是否都是0，如果不是直接返回-1；
2.然后判断矩阵的规格，如果是1*1的矩阵，直接返回1；
3.然后开始bfs搜索，每次我们可以朝着八个方向走出一步，所以定义一个方向数组。
int[][] directions={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};4.然后套用dfs的模板即可。
while(!queue.isEmpty()){int size=queue.size();for(int i=0;i<size;i++){int[] next=queue.poll();//循环遍历这一层的元素for(int[] direc:directions){int newX=next[0]+direc[0];int newY=next[1]+direc[1];if(newX>=0&&newX<m&&newY>=0&&newY<n&&!visited[newX][newY]&&grid[newX][newY]==0){if(newX==m-1&&newY==n-1)return step+1;visited[newX][newY]=true;queue.add(new int[]{newX,newY});}}}step++; }
代码：
class Solution {boolean[][] visited;int m;int n;int[][] directions={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};public int shortestPathBinaryMatrix(int[][] grid) {if(grid[0][0]!=0||grid[grid.length-1][grid[0].length-1]!=0)return -1;m=grid.length;n=grid[0].length;if(m == 1 && n == 1 && grid[0][0] == 0) return 1;visited=new boolean[m][n];Queue<int[]> queue=new ArrayDeque<int[]>();queue.add(new int[]{0,0});visited[0][0]=true;int step=1;while(!queue.isEmpty()){int size=queue.size();for(int i=0;i<size;i++){int[] next=queue.poll();//循环遍历这一层的元素for(int[] direc:directions){int newX=next[0]+direc[0];int newY=next[1]+direc[1];if(newX>=0&&newX<m&&newY>=0&&newY<n&&!visited[newX][newY]&&grid[newX][newY]==0){if(newX==m-1&&newY==n-1)return step+1;visited[newX][newY]=true;queue.add(new int[]{newX,newY});}}}step++; }return -1;}
}二、迷宫中离入口最近的出口
给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。1.同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
每一步操作，2.你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。3.你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。
思路：
1.首先，这是一个单源点的bfs搜索题，for循环不断遍历每一次搜索能到达的点，然后把这些点加入queue队列中。
2.然后再次for循环遍历这些队列，到达出口的判定条件是:在第一行或者最后一行 第一列或者最后一列。
代码：
class Solution {int[][] directions = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };public int nearestExit(char[][] maze, int[] entrance) {int m = maze.length;int n = maze[0].length;boolean[][] visited = new boolean[m][n];Queue<int[]> queue = new ArrayDeque<int[]>();queue.add(entrance);visited[entrance[0]][entrance[1]] = true;int steps = 0;while (!queue.isEmpty()) {int size=queue.size();for (int i = 0; i < size; i++) {int[] current = queue.poll();for (int[] dir : directions) {int newX = current[0] + dir[0];int newY = current[1] + dir[1];if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY] && maze[newX][newY] == '.') {if (newX == 0 || newX == m - 1 || newY == 0 || newY == n - 1)return steps+1;visited[newX][newY] = true;queue.add(new int[] { newX, newY });}}}steps++;}return -1;}
}
多源点系列:
三、地图分析
你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。
请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
思路：
要求0到最近的1的距离的最大值。我们可以计算1到最近的0的距离的最大值。
多源点问题:
1.首先我们将所有值为1的点都加入到队列中，然后将值为0的点的值都改为-1；(这样就不用使用visited数组来记忆化了)
2.然后对队列循环，当遇到-1的时候，我们将它标记一下。然后继续寻找。最后返回step-1
（为什么是step-1呢，因为在最后一次查找的时候，已经无法再向外层扩展了，但还是++，所以最后返回的时候应该再减去1）
代码：
class Solution {int[][] directions = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };int[][] grid;int m;int n;public int maxDistance(int[][] grid) {this.grid = grid;m = grid.length;n = grid[0].length;Queue<int[]> queue = new ArrayDeque<int[]>();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1) {queue.add(new int[] { i, j });}else{grid[i][j]=-1;}}}if(queue.size()==0||queue.size()==n*n)return -1;int step=0;while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {int[] current = queue.poll();for (int[] dirc : directions) {int newX = current[0] + dirc[0];int newY = current[1] + dirc[1];if (newX >= 0 && newX < m && newY >= 0 && newY < n &&grid[newX][newY]==-1) {grid[newX][newY]=step+1;queue.add(new int[] { newX, newY });}}}step++;}return step-1;}
}四、01矩阵
给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1：
输入：mat = [[0,0,0],[0,1,0],[0,0,0]] 输出：[[0,0,0],[0,1,0],[0,0,0]]
思路：
题目中要求每一个格子距离0的最小值。我们还是逆向思维，以1为主，找距离最小的0。
多源点问题：1.首先将所有的值为1的点都加入队列中，然后将值为0的点赋值为不能达到的值
2.然后套用模板，开始遍历队列。如果遇到值==-1的点，那我们就将这个格子的值赋为step;
3.最后返回格子即可。(我们在格子上原地修改)
代码：
class Solution {public int[][] updateMatrix(int[][] mat) {int[][] directions={{0,-1},{0,1},{-1,0},{1,0}};int m=mat.length;int n=mat[0].length;boolean[][] visited=new boolean[m][n];Queue<int[]> queue=new ArrayDeque<int[]>();for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(mat[i][j]==0)queue.add(new int[]{i,j});else mat[i][j]=-1;//先将值为1的位置赋为-1}}int step=1;while(!queue.isEmpty()){int size=queue.size();for(int i=0;i<size;i++){int[] current=queue.poll();for(int[] dirc:directions){int newX=current[0]+dirc[0];int newY=current[1]+dirc[1];if(newX>=0&&newX<m&&newY>=0&&newY<n&&!visited[newX][newY]&&mat[newX][newY]==-1){mat[newX][newY]=step;queue.add(new int[]{newX,newY}); }}}step++;}return mat;}
}
