C++刷leetcode（1293. 网格中的最短路径）【状态压缩】【广度优先搜索】
本帖最后由 糖逗 于 2021-3-3 20:00 编辑题目描述：
给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。
如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1。
示例 1：
输入：
grid =
[,
,
,
,
],
k = 1
输出：6
解释：
不消除任何障碍的最短路径是 10。
消除位置 (3,2) 处的障碍后，最短路径是 6 。该路径是 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).
示例 2：
输入：
grid =
[,
,
],
k = 1
输出：-1
解释：
我们至少需要消除两个障碍才能找到这样的路径。
提示：
grid.length == m
grid.length == n
1 <= m, n <= 40
1 <= k <= m*n
grid == 0 or 1
grid == grid == 0
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-path-in-a-grid-with-obstacles-elimination
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
private:
struct State{
int cur_x;
int cur_y;
int use;
State(int a, int b, int c):cur_x(a), cur_y(b), use(c){}
};
vector<vector<int> >direct = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
public:
int shortestPath(vector<vector<int>>& grid, int k) {
int len1 = grid.size(), len2 = grid.size();
if(k >= len1 + len2 - 3) return len1 + len2 - 2;//即使期间全部有障碍，也可直接走最短的直角
vector<vector<vector<bool> > >visit(len1, vector<vector<bool> >(len2, vector<bool>(k+1 , false)));
//广度优先搜索
queue<State>store;
store.push(State(0, 0, 0));
int res = 0;
while(!store.empty()){
int size = store.size();
for(int i = 0; i < size; i++){
State temp = store.front();
store.pop();
int cur_x = temp.cur_x;
int cur_y = temp.cur_y;
int use = temp.use;
if(cur_x == len1 - 1 && cur_y == len2 - 1 && use <= k){
return res;
}
if(visit == true)continue;
visit = true;
for(int i = 0; i < 4; i++){
int next_x = cur_x + direct;
int next_y = cur_y + direct;
if(next_x >= 0 && next_x < len1 && next_y >= 0 && next_y < len2){
if(grid == 1 && use <= k-1){
store.push(State(next_x, next_y, use+1));
}else if(grid == 0){
store.push(State(next_x, next_y, use));
}
}
}
}
res++;
}
return -1;
}
}; 该类型题有固定模板
页:
[1]