鱼C论坛

 找回密码
 立即注册
查看: 3821|回复: 1

[技术交流] C++刷leetcode(1293. 网格中的最短路径)【状态压缩】【广度优先搜索】

[复制链接]
发表于 2021-3-3 19:58:53 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 糖逗 于 2021-3-3 20:00 编辑

题目描述:
  1. 给你一个 m * n 的网格,其中每个单元格不是 0(空)就是 1(障碍物)。每一步,您都可以在空白单元格中上、下、左、右移动。

  2. 如果您 最多 可以消除 k 个障碍物,请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径,并返回通过该路径所需的步数。如果找不到这样的路径,则返回 -1。

  3.  

  4. 示例 1:

  5. 输入:
  6. grid =
  7. [[0,0,0],
  8.  [1,1,0],
  9. [0,0,0],
  10.  [0,1,1],
  11. [0,0,0]],
  12. k = 1
  13. 输出:6
  14. 解释:
  15. 不消除任何障碍的最短路径是 10。
  16. 消除位置 (3,2) 处的障碍后,最短路径是 6 。该路径是 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).
  17.  

  18. 示例 2:

  19. 输入:
  20. grid =
  21. [[0,1,1],
  22.  [1,1,1],
  23.  [1,0,0]],
  24. k = 1
  25. 输出:-1
  26. 解释:
  27. 我们至少需要消除两个障碍才能找到这样的路径。
  28.  

  29. 提示:

  30. grid.length == m
  31. grid[0].length == n
  32. 1 <= m, n <= 40
  33. 1 <= k <= m*n
  34. grid[i][j] == 0 or 1
  35. grid[0][0] == grid[m-1][n-1] == 0

  36. 来源:力扣(LeetCode)
  37. 链接:https://leetcode-cn.com/problems/shortest-path-in-a-grid-with-obstacles-elimination
  38. 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码


  1. class Solution {
  2. private:
  3.     struct State{
  4.         int cur_x;
  5.         int cur_y;
  6.         int use;
  7.         State(int a, int b, int c):cur_x(a), cur_y(b), use(c){}
  8.     };
  9.     vector<vector<int> >direct = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
  10. public:
  11.     int shortestPath(vector<vector<int>>& grid, int k) {
  12.         int len1 = grid.size(), len2 = grid[0].size();
  13.         if(k >= len1 + len2 - 3) return len1 + len2 - 2;//即使期间全部有障碍,也可直接走最短的直角
  14.         vector<vector<vector<bool> > >visit(len1, vector<vector<bool> >(len2, vector<bool>(k+1 , false)));
  15.         //广度优先搜索
  16.         queue<State>store;
  17.         store.push(State(0, 0, 0));

  18.         int res = 0;
  19.         while(!store.empty()){
  20.             int size = store.size();
  21.             for(int i = 0; i < size; i++){
  22.                 State temp = store.front();
  23.                 store.pop();
  24.                 int cur_x = temp.cur_x;
  25.                 int cur_y = temp.cur_y;
  26.                 int use = temp.use;
  27.                 if(cur_x == len1 - 1 && cur_y == len2 - 1 && use <= k){
  28.                     return res;
  29.                 }

  30.                 if(visit[cur_x][cur_y][use] == true)continue;
  31.                 visit[cur_x][cur_y][use] = true;

  32.                 for(int i = 0; i < 4; i++){
  33.                     int next_x = cur_x + direct[i][0];
  34.                     int next_y = cur_y + direct[i][1];
  35.                     if(next_x >= 0 && next_x < len1 && next_y >= 0 && next_y < len2){
  36.                         if(grid[next_x][next_y] == 1 && use <= k-1){
  37.                             store.push(State(next_x, next_y, use+1));
  38.                         }else if(grid[next_x][next_y] == 0){
  39.                             store.push(State(next_x, next_y, use));
  40.                         }
  41.                     }
  42.                 }
  43.             }
  44.             res++;
  45.         }
  46.         return -1;
  47.     }
  48. };
复制代码

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2021-3-3 19:59:25 | 显示全部楼层
该类型题有固定模板
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-3 10:08

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表