网格问题（回溯/DP）：最短路径（排除障碍物）+路径数量+路径最大/小和+判断路径存在 |
您所在的位置：网站首页 › 10×10网格图 › 网格问题（回溯/DP）：最短路径（排除障碍物）+路径数量+路径最大/小和+判断路径存在 |
网格问题（回溯/DP）：最短路径（排除障碍物）+路径数量+路径最大/小和+判断路径存在
|
一、网格中的最短路径
1.1 可以消除障碍物
LeetCode1293：网格中的最短路径 给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1。 本题比较麻烦些，增加了障碍物且可以有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 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 int xNew = x + dx[j]; int yNew = y + dy[j]; // 越界 if (xNew = m || 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 40 || n 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 for(int j=0;j //移动的四个方向 int[] dx = {1, 0, -1, 0}; int[] dy = {0, 1, 0, -1}; //用来储存距离到起始点最短路径的二维数组 int[][] d = new int [map.length][map[0].length]; //储存未进行处理的点 Queue que = new LinkedList(); //将所有的位置都初始化为最大 for(int i = 0; i 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 //如果可以走，则将该点的距离加1 d[ny][nx] = d[current[0]][current[1]] + 1; //并将该点放入队列等待下次处理 int[] c = {ny, nx}; que.offer(c); } } } return d[end[0]][end[1]]; } } 二、网格的路径数量——DPLeetCode63：不同的路径 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？ LeetCode47：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof 求上下位置最大的那个，加上当前位置的数，作为到达该位置的最大和，即dp[i][j] 给定一个包含非负整数的 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 dp[0][i] = dp[0][i-1] + dp[0][i]; } for(int i=1;i 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 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 = board.length || 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 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 |
【本文地址】
今日新闻 |
推荐新闻 |