网格问题（回溯/DP）：最短路径（排除障碍物）+路径数量+路径最大/小和+判断路径存在_计算障碍物偏离路径轨迹最大最小距离_等待的疲倦的博客

一、网格中的最短路径

1.1 可以消除障碍物

LeetCode1293：网格中的最短路径
给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。如果您最多可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1。
在这里插入图片描述
class Solution {
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();//网格的长
		int n = sc.nextInt();//网格的宽
		int k = sc.nextInt();
        int[][] grid = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                grid[i][j] = sc.nextInt();
        System.out.println(shortestPath(grid,k));
    public int shortestPath(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        if(k >= m + n -3) return m + n - 2;
        boolean[][] visited = new boolean[m][n];
        int res = backtrack(grid,0,0,m,n,0,k,visited);
        return res == Integer.MAX_VALUE ? -1 : res;
    public int backtrack(int[][] grid,int i,int j,int m,int n,int count,int k,boolean[][] visited){
        if(i < 0 || i >= m || j < 0 || j >= n) return Integer.MAX_VALUE;//递归出口
        if(i == m-1 && j == n-1) return count;//结果
        if(visited[i][j]) return Integer.MAX_VALUE;
        //排除障碍物
        if(grid[i][j] == 1){
            if(k > 0) k--;
            else return Integer.MAX_VALUE;
        visited[i][j] = true;
        //取4个方向可能路径的最小值返回
        int min4 = Integer.MAX_VALUE;
        min4 = Math.min(min4,backtrack(grid,i-1,j,m,n,count+1,k,visited));
        min4 = Math.min(min4,backtrack(grid,i+1,j,m,n,count+1,k,visited));
        min4 = Math.min(min4,backtrack(grid,i,j-1,m,n,count+1,k,visited));
        min4 = Math.min(min4,backtrack(grid,i,j+1,m,n,count+1,k,visited));
        visited[i][j] = false;
        return min4;
【法二】visited访问标记数组三维扩展 （用于比较）
 
本题比较麻烦些，增加了障碍物且可以有k次机会消除，单纯有障碍物就是标准的BFS处理即可，但有k次消除障碍物，就需要增加一个维度来记录同一个节点被访问的时候 已经使用消除障碍物的次数。： 
链接：作者：jin-129 
public int shortestPath(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        // 非法参数处理
        if (validateInputParams(k, m, n)) {
            return -1;
        // 特殊场景处理
        if (m == 1 && n == 1) {
            return 0;
        // BFS搜索节点访问标识, 此题要求有k个消除障碍的机会，所以每个节点除了标记是否被访问过
        // 还要记录搜索到此节点时消除了几个障碍。消除相同障碍的下一层节点 可以剪枝（因为有相同代价更早的节点了）




    

        // 例子：k=1, BFS是按层级来的，绕道的层级扩展越多
        // 坐标(0,2)可以为消除(0,1)障碍过来的 visited[0][2][1] = 1，搜索层级为2
        // 也可能为不消除任何障碍过来的 visited[0][2][0] = 1，层级为6，为扩展搜索不通障碍消除数提供区分
        // 0 1 0 0 0 1 0 0
        // 0 1 0 1 0 1 0 1
        // 0 0 0 1 0 0 1 0
        // 二维标记位置，第三维度标记 到此节点的路径处理障碍总个数
        int[][][] visited = new int[m][n][k+1];
        // 初始步数为0，m=n=1的特殊场景已处理
        int minSteps = 0;
        // 初始位置标记已访问
        visited[0][0][0] = 1;
        Queue<Point> queue = new LinkedList<>();
        Point startPoint = new Point(0, 0, 0);
        queue.offer(startPoint);
        // 定义四个方向移动坐标
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        // BFS搜索-队列遍历
        while (!queue.isEmpty()) {
            minSteps++;
            // BFS搜索-遍历相同层级下所有节点
            // 当前队列长度一定要在循环外部定义，循环内部有插入对列操作
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Point current = queue.poll();
                int x = current.x;
                int y = current.y;
                int oneCount = current.oneCount;
                // 对当前节点四个方向进行识别处理
                for (int j = 0; j < 4; j++) {
                    int xNew = x + dx[j];
                    int yNew = y + dy[j];
                    // 越界
                    if (xNew < 0 || xNew >= m || yNew < 0 || yNew >= n) {
                        continue;
                    // 搜索到目标节点则直接返回结果
                    if (xNew == m - 1 && yNew == n - 1) {
                        return minSteps;
                    // 穿越障碍次数已满
                    if (grid[xNew][yNew] == 1 && oneCount >= k) {
                        continue;
                    int oneCountNew = grid[xNew][yNew] == 1 ? oneCount + 1 : oneCount;
                    // 四个方向节点是否被访问过（第三维度）
                    if (visited[xNew][yNew][oneCountNew] == 1) {
                        continue;
                    } else {
                        // 未被访问过且可以走的节点标记为访问过，对下一步节点确认状态非常重要
                        // 将下一层级节点入队列标记为已访问，可以剪枝更多节点，节省计算耗时
                        visited[xNew][yNew][oneCountNew] = 1;
                    queue.offer(new Point(xNew, yNew, oneCountNew));
        // BFS没搜索到目标，返回-1
        return -1;
    private boolean validateInputParams(int k, int m, int n) {
        return m > 40 || m < 1 || n > 40 || n < 1 || k < 1 || k > m * n;
    class Point {
        int x;
        int y;
        int oneCount;
        public Point(int x, int y, int oneCount) {
            this.x = x;
            this.y = y;
            this.oneCount = oneCount;
1.2 不能消除障碍物（走迷宫）
 
 第一行代表迷宫地图的行列数
 第二行代表起点，
 第三行代表终点 后面即地图，
 x代表障碍物，o代表通路。 
 最短路径的值，走一步 + 1 
输入：
 5 5
 0 0
 2 2
 ooooo
 oxxxo
 oxooo
 oxxxo
 ooooo
 输出：
 8 
import java.util.*;
public class Main1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();//n行
            int m = sc.nextInt();//m列
			int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int[] begin = {x1,y1};//起点
            int x2 = sc.




    
nextInt();
            int y2 = sc.nextInt();
            int[] end = {x2,y2};  //终点
            char[][] map = new char[n][m];
            String[] s = new String[n];
			for(int i = 0;i < n;i++){
				s[i] = sc.next();
            for(int i = 0;i < n;i++){
                for(int j=0;j < m;j++){
                    map[i][j] = s[i].charAt(j);
            //System.out.println(Arrays.toString(map));
            System.out.println(bfs(map,begin,end));
    public static int bfs(char[][] map, int[] begin, int[] end) {
		//移动的四个方向
		int[] dx = {1, 0, -1, 0};
		int[] dy = {0, 1, 0, -1};
		//用来储存距离到起始点最短路径的二维数组
		int[][] d = new int [map.length][map[0].length];
		//储存未进行处理的点
		Queue<int[]> que = new LinkedList<int[]>();
		//将所有的位置都初始化为最大
		for(int i = 0; i < d.length; i++) {
			for(int j = 0; j < d[0].length; j++) {
				d[i][j] = Integer.MAX_VALUE;
		//将起始点放入队列
		que.offer(begin);
		//将起始点最短路径设为0
		d[ begin[0] ][ begin[1] ] = 0;
		//一直循环直到队列为空
		while(!que.isEmpty()) {
			//取出队列中最前端的点
			int[] current = que.poll();
			//如果是终点则结束
			if(current[0] == end[0] && current[1] == end[1]) break;
			//四个方向循环
			for(int i = 0; i < 4; i++) {
				int ny = current[0] + dy[i];
				int nx = current[1] + dx[i];
				//判断是否可以走
				if(ny >= 0 && ny < d.length && nx >= 0 && nx < d[0].length && map[ny][nx] != 'x' && d[ny][nx] == Integer.MAX_VALUE) {
					//如果可以走，则将该点的距离加1
					d[ny][nx] = d[current[0]][current[1]] + 1;
					//并将该点放入队列等待下次处理
					int[] c = {ny, nx};
					que.offer(c);
		return d[end[0]][end[1]];
二、网格的路径数量——DP
 
LeetCode63：不同的路径
  
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid.length==0) return 0;
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        int[][] dp = new




    
 int[row][col];//走到该格的方法数
        //初始化第一行和第一列，没有障碍物就设置为1
        for(int i=0; i<row && obstacleGrid[i][0] == 0; i++){
            dp[i][0] = 1;
        for(int j=0; j<col && obstacleGrid[0][j] == 0; j++){
            dp[0][j] = 1;
        //递推，如果dp的左边一个和上边一个都为1，那么这格的数字就为2
        //如果左边为1，上面为0，那么这个为1，如果网格此处有阻碍，那么dp为0
        for(int i=1;i<row;i++){
            for(int j=1;j<col;j++){
                if(obstacleGrid[i][j] == 0){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
        return dp[row-1][col-1];
三、网格路径最大和
 
（1）滚动数组方案（比较难想到）
 
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
 LeetCode47：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof
  
class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        //滚动数组方案
        int[] dp = new int[n+1];//记录实时的求和结果
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[j] = Math.max(dp[j],dp[j-1]) + grid[i-1][j-1];
        return dp[n];
（2）二维数组DP
 
求上下位置最大的那个，加上当前位置的数，作为到达该位置的最大和，即dp[i][j]
  
class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = grid;//记录棋盘中，当前位置的和
        //初始化dp
        for(int i=1;i<n;i++){//第一行挨个求和，初始化
            dp[0][i] = dp[0][i] + dp[0][i-1];
        for(int j=1;j<m;j++){//第一列挨个求和，初始化
            dp[j][0] = dp[j][0] + dp[j-1][0];
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) + grid[i][j];
        return dp[m-1][n-1];//到达棋盘最后一个位置的和
四、网格路径最小和
 
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 说明：每次只能向下或者向右移动一步。
 示例: 
输入:
 [
 [1,3,1],
 [1,5,1],
 [4,2,1]
 ]
 输出: 7
 解释: 因为路径 1→3→1→1→1 的总和最小。 
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = grid;
        for(int i=1;i<m;i++){
            dp[i][0]




    
 = dp[i-1][0] + dp[i][0];
        for(int i=1;i<n;i++){
            dp[0][i] = dp[0][i-1] + dp[0][i];
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
        return dp[m-1][n-1];
五、搜索单词是否在网格中
 
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 原题链接：https://leetcode-cn.com/problems/word-search 
 board =
 [
 [‘A’,‘B’,‘C’,‘E’],
 [‘S’,‘F’,‘C’,‘S’],
 [‘A’,‘D’,‘E’,‘E’]
 ] 
 给定 word = “ABCCED”, 返回 true
 给定 word = “SEE”, 返回 true
 给定 word = “ABCB”,返回 false 
class Solution {
    public boolean exist(char[][] board, String word) {
        char[] c = word.toCharArray();
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(board[i][j]==c[0]){ //找到起点
                    if(dfs(board,i,j,c,0)){
                        return true;
        return false;
    public boolean dfs(char[][] board,int row,int col,char[] c,int index){
        if(row < 0 || row >= board.length || col < 0 || col >= board[0].length){//递归出口
            return false;
        if(index == c.length - 1 && board[row][col] == c[index]){ //成功条件
            return true;
        if(board[row][col] != c[index]){
            return false;
        board[row][col] = '-';//将成功匹配的位置替换为-
        boolean res = dfs(board,row,col-1,c,index+1) || dfs(board,row,col+1,c,index+1) || dfs(board,row-1,col,c,index+1) || dfs(board,row+1,col,c,index+1);
        board[row][col] = c[index];//在return前将-替换回c[index]
        return res;
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格**。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子**。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
 [
 [“a”,“b”,“c”,“e”],
 [“s”,“f”,“c”,“s”],
 [“a”,“d”,“e”,“e”]
 ] 
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。 
示例 1：
 输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
 输出：true 
示例 2：
 输入：board = [[“a”,“b”],[“c”,“d”]], word = “abcd”
 输出：false 
class Solution {
    public boolean exist(char[][] board, String word) {
        if(board == null || board == null || board.length == 0 || board[0].length == 0 || word == null || word.equals("")){
            return false;
        boolean[][] isVisited = new boolean[board.length][board[0].length];
        char[] c = word.toCharArray();
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(board[i][j] == c[0]){
                    if(bfs(board,i,j,isVisited,c,0)){
                        return true;
        return false;
    public boolean bfs(char[][] board,int i,int j,boolean[][] isVisited,char[] c,int index){
        if(index == c.length){//成功条件
            return true;
        if(i<0 || j<0 || i==board.length || j==board[0].length || isVisited[i][j] || board[i][j]!=c[index]){
            return false;
        isVisited[i][j] = true;
        boolean res = bfs(board,i+1,j,isVisited,c,index+1) 
                   || bfs(board,i-1,j,isVisited,c,index+1)
                   || bfs(board,i,j+1,isVisited,c,index+1)
                   || bfs(board,i,j-1,isVisited,c,index+1);
        isVisited[i][j] = false;
        return res;
                    一、网格中的最短路径——回溯LeetCode1293：网格中的最短路径给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1。class Solution {    public int shortestPath(int[][] grid, int k)
				javafx-最短路径挑战
最短路径挑战
该应用程序将生成一个像素网格。 在网格内，将有一组节点。 一个节点代表网格上的一个像素。 节点由其节点编号唯一标识，并且它在网格中的位置由 (x,y) 坐标表示。
 您的挑战是找到所有节点之间的最短路径。
 必须至少访问所有节点一次。 一些节点可能位于同一坐标上。
 要创建解决方案，请实现抽象类 com.gmjm.challenge1.ChallengeSolution。 将您的解决方案放在 com.gmjm.challenge1.solutions 目录中。 该应用程序将在使用反射加载时找到您的解决方案，并且应出现在解决方案列表中。
 您的解决方案将采用 Node 对象列表的形式。 列表的顺序表示节点将被遍历的顺序。
 解分析器从头到尾遍历节点。 如果两个节点位于同一个坐标上，您仍然需要将两者都包含在列表中以获得访问它们的信用。
				给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。
如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1。
示例 1：
grid =
[[0,0,0],
[1,1,0],
[0,0,0],
[0,1,1],
[0,0,0]],
k = 1
不消除任何障碍的最短路径是 10。
				文章目录1. 单调栈2. 区间问题3. 最大子序和4. 滑动窗口5. 优先队列/堆6. 岛屿问题（网格DFS）7. 二分查找8. 栈9. HashSet/HashMap10. 位运算11. 链表12. 二叉树13. 设计类14. 快慢指针15. 回文16. 数字操作17. 双指针18. BFS其他
1. 单调栈
496. 下一个更大元素 I
402. 移掉K位数字
581. 最短无序连续子数组
739. 每日温度
901. 股票价格跨度
1081. 不同字符的最小子序列
				背景：还是秋招刷题
参考：https://www.bilibili.com/video/av57064859?from=search&seid=769707923257914088 （B站果然是学习的网站）
题目：一个M*N网格，从左下角（0，0）出发，走到右上角。只能向上走和向右走，有多少条路径？
一、无障碍物版本
解题思路：
不管怎样，都要往上走M-1次，往右走N-1次，且一共一定...
				在 Python 中，您可以使用轮廓线算法来建立 AGV 小车的路径和地图。
下面是一个示例代码，假设您已经有了一张网格地图，其中 0 表示可以行走的路径，1 表示障碍物：
```python
def build_path(grid):
    # 定义起点和终点
    start = (0, 0)
    end = (len(grid) - 1, len(grid[0]) - 1)
    # 创建一个队列，用于存储将要搜索的点
    queue = [start]
    # 创建一个字典，用于存储每个点的父节点
    parents = {start: None}
    # 当队列不为空时，进行循环
    while queue:
        # 取出队列的第一个点
        current = queue.pop(0)
        # 如果当前点是终点，则退出循环
        if current == end:
            break
        # 搜索当前点的上下左右四个方向
        for direction in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            # 计算下一个点的坐标
            x, y = current[0] + direction[0], current[1] + direction[1]
            # 如果下一个点越界或者是障碍物，则跳过
            if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]) or grid[x][y] == 1:
                continue
            # 否则，将下一个点加入队列中
            next = (x, y)
            queue.append(next)
            # 并将下一个点的父节点设置为当前点
            parents[next] = current
    # 创建一个列表，用于存储路径上的所有