C++刷leetcode（1293. 网格中的最短路径）【状态压缩】【广度优先搜索】

糖逗

题目描述：

1. 给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。
   
2. 
   
3. 如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1。
   
4. 
   
5.  
   
6. 
   
7. 示例 1：
   
8. 
   
9. 输入：
   
10. grid =
    
11. [[0,0,0],
    
12.  [1,1,0],
    
13. [0,0,0],
    
14.  [0,1,1],
    
15. [0,0,0]],
    
16. k = 1
    
17. 输出：6
    
18. 解释：
    
19. 不消除任何障碍的最短路径是 10。
    
20. 消除位置 (3,2) 处的障碍后，最短路径是 6 。该路径是 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).
    
21.  
    
22. 
    
23. 示例 2：
    
24. 
    
25. 输入：
    
26. grid =
    
27. [[0,1,1],
    
28.  [1,1,1],
    
29.  [1,0,0]],
    
30. k = 1
    
31. 输出：-1
    
32. 解释：
    
33. 我们至少需要消除两个障碍才能找到这样的路径。
    
34.  
    
35. 
    
36. 提示：
    
37. 
    
38. grid.length == m
    
39. grid[0].length == n
    
40. 1 <= m, n <= 40
    
41. 1 <= k <= m*n
    
42. grid[i][j] == 0 or 1
    
43. grid[0][0] == grid[m-1][n-1] == 0
    
44. 
    
45. 来源：力扣（LeetCode）
    
46. 链接：https://leetcode-cn.com/problems/shortest-path-in-a-grid-with-obstacles-elimination
    
47. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

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. 
    
19.         int res = 0;
    
20.         while(!store.empty()){
    
21.             int size = store.size();
    
22.             for(int i = 0; i < size; i++){
    
23.                 State temp = store.front();
    
24.                 store.pop();
    
25.                 int cur_x = temp.cur_x;
    
26.                 int cur_y = temp.cur_y;
    
27.                 int use = temp.use;
    
28.                 if(cur_x == len1 - 1 && cur_y == len2 - 1 && use <= k){
    
29.                     return res;
    
30.                 }
    
31. 
    
32.                 if(visit[cur_x][cur_y][use] == true)continue;
    
33.                 visit[cur_x][cur_y][use] = true;
    
34. 
    
35.                 for(int i = 0; i < 4; i++){
    
36.                     int next_x = cur_x + direct[i][0];
    
37.                     int next_y = cur_y + direct[i][1];
    
38.                     if(next_x >= 0 && next_x < len1 && next_y >= 0 && next_y < len2){
    
39.                         if(grid[next_x][next_y] == 1 && use <= k-1){
    
40.                             store.push(State(next_x, next_y, use+1));
    
41.                         }else if(grid[next_x][next_y] == 0){
    
42.                             store.push(State(next_x, next_y, use));
    
43.                         }
    
44.                     }
    
45.                 }
    
46.             }
    
47.             res++;
    
48.         }
    
49.         return -1;
    
50.     }
    
51. };

复制代码

糖逗

该类型题有固定模板