|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 糖逗 于 2021-3-3 20:00 编辑
题目描述:
- 给你一个 m * n 的网格,其中每个单元格不是 0(空)就是 1(障碍物)。每一步,您都可以在空白单元格中上、下、左、右移动。
- 如果您 最多 可以消除 k 个障碍物,请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径,并返回通过该路径所需的步数。如果找不到这样的路径,则返回 -1。
-  
- 示例 1:
- 输入:
- grid =
- [[0,0,0],
-  [1,1,0],
- [0,0,0],
-  [0,1,1],
- [0,0,0]],
- k = 1
- 输出:6
- 解释:
- 不消除任何障碍的最短路径是 10。
- 消除位置 (3,2) 处的障碍后,最短路径是 6 。该路径是 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).
-  
- 示例 2:
- 输入:
- grid =
- [[0,1,1],
-  [1,1,1],
-  [1,0,0]],
- k = 1
- 输出:-1
- 解释:
- 我们至少需要消除两个障碍才能找到这样的路径。
-  
- 提示:
- grid.length == m
- grid[0].length == n
- 1 <= m, n <= 40
- 1 <= k <= m*n
- grid[i][j] == 0 or 1
- grid[0][0] == grid[m-1][n-1] == 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[0].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[cur_x][cur_y][use] == true)continue;
- visit[cur_x][cur_y][use] = true;
- for(int i = 0; i < 4; i++){
- int next_x = cur_x + direct[i][0];
- int next_y = cur_y + direct[i][1];
- if(next_x >= 0 && next_x < len1 && next_y >= 0 && next_y < len2){
- if(grid[next_x][next_y] == 1 && use <= k-1){
- store.push(State(next_x, next_y, use+1));
- }else if(grid[next_x][next_y] == 0){
- store.push(State(next_x, next_y, use));
- }
- }
- }
- }
- res++;
- }
- return -1;
- }
- };
复制代码 |
|