网格问题（回溯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; } }