{"id":5966,"date":"2019-12-14T20:19:11","date_gmt":"2019-12-15T04:19:11","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5966"},"modified":"2019-12-15T00:03:06","modified_gmt":"2019-12-15T08:03:06","slug":"leetcode-1293-shortest-path-in-a-grid-with-obstacles-elimination","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1293-shortest-path-in-a-grid-with-obstacles-elimination\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1293. Shortest Path in a Grid with Obstacles Elimination"},"content":{"rendered":"\n

iven a m * n<\/code> grid, where each cell is either 0<\/code> (empty) or 1<\/code> (obstacle). In one step, you can move up, down, left or right from and to an empty cell.<\/p>\n\n\n\n

Return the minimum number of steps to walk from the upper left corner (0, 0)<\/code> to the lower right corner (m-1, n-1)<\/code> given that you can eliminate at most<\/strong> k<\/code> obstacles. If it is not possible to find such walk return -1.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> \ngrid = \n[[0,0,0],\n [1,1,0],\n [0,0,0],\n [0,1,1],\n [0,0,0]], \nk = 1\nOutput:<\/strong> 6\nExplanation: \n<\/strong>The shortest path without eliminating any obstacle is 10. \nThe shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2)<\/strong> -> (4,2)<\/code>.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> \ngrid = \n[[0,1,1],\n [1,1,1],\n [1,0,0]], \nk = 1\nOutput:<\/strong> -1\nExplanation: \n<\/strong>We need to eliminate at least two obstacles to find such a walk.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • grid.length == m<\/code><\/li>
  • grid[0].length == n<\/code><\/li>
  • 1 <= m, n <= 40<\/code><\/li>
  • 1 <= k <= m*n<\/code><\/li>
  • grid[i][j] == 0 or<\/strong> 1<\/code><\/li>
  • grid[0][0] == grid[m-1][n-1] == 0<\/code><\/li><\/ul>\n\n\n\n
    Solution: BFS<\/strong><\/h2>\n\n\n\n
    State: (x, y, k) where k is the number of obstacles along the path.<\/p>\n\n\n\n
    Time complexity: O(m*n*k)
    Space complexity: O(m*n*k)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua, 8 ms, 10.5 MB\nclass Solution {\npublic:\n  int shortestPath(vector>& grid, int k) {\n    const vector dirs{0, 1, 0, -1, 0};\n    const int n = grid.size();\n    const int m = grid[0].size();\n    vector> seen(n, vector(m, INT_MAX));\n    queue> q; \n    int steps = 0;\n    q.emplace(0, 0, 0);\n    seen[0][0] = 0;\n    while (!q.empty()) {\n      int size = q.size();\n      while (size--) {\n        int cx, cy, co;\n        tie(cx, cy, co) = q.front(); q.pop();         \n        if (cx == m - 1 && cy == n - 1) return steps;\n        for (int i = 0; i < 4; ++i) {\n          int x = cx + dirs[i];\n          int y = cy + dirs[i + 1];\n          if (x < 0 || y < 0 || x >= m || y >= n) continue;\n          int o = co + grid[y][x];\n          if (o >= seen[y][x] || o > k) continue;            \n          seen[y][x] = o;\n          q.emplace(x, y, o);\n        }\n      }\n      ++steps;\n    }\n    return -1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    Solution 2: DP<\/strong><\/h2>\n\n\n\n
    Time complexity: O(mnk)
    Space complexity: O(mnk)<\/p>\n\n\n\n
    \n
    Bottom-Up<\/h2>\n
    \n\n
    \n\/\/ AC 236 ms\nclass Solution {\npublic:\n  int shortestPath(vector>& grid, int k) {\n    constexpr int kInf = 1e9;\n    const int m = grid.size();\n    const int n = grid[0].size();\n    vector>> dp(m + 2, vector>(n + 2, vector(k + 1, kInf)));\n    dp[1][1][0] = 0;\n    for (int s = 0; s < 3; ++s)\n      for (int i = 1; i <= m; ++i)\n        for (int j = 1; j <= n; ++j) {\n          const int o = grid[i - 1][j - 1];\n          for (int z = 0; z + o <= k; ++z)\n            dp[i][j][z + o] = min(dp[i][j][z + o],\n                                  min({dp[i - 1][j][z],\n                                       dp[i][j - 1][z],\n                                       dp[i + 1][j][z],\n                                       dp[i][j + 1][z]}) + 1);\n        }\n    int ans = *min_element(begin(dp[m][n]), end(dp[m][n]));\n    return ans >= kInf ? -1 : ans;\n  }\n};\n<\/pre>\n\n<\/div>
    Top-Down<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  int shortestPath(vector>& grid, int K) {\n    constexpr int kInf = 1e9;\n    const vector dirs{0, 1, 0, -1, 0};\n    const int m = grid.size();\n    const int n = grid[0].size();\n    vector>> mem(m + 2, vector>(n + 2, vector(K + 1, -1)));\n    vector> seen(m + 2, vector(n + 2));    \n    function dp = [&](int x, int y, int k) {      \n      if (x < 1 || x > n || y < 1 || y > m || k < 0 || seen[y][x]) return kInf;\n      if (x == 1 && y == 1) return 0;\n      if (mem[y][x][k] != -1) return mem[y][x][k];\n      seen[y][x] = 1;\n      int ans = kInf;\n      for (int i = 0; i < 4; ++i)\n        ans = min(ans, 1 + dp(x + dirs[i], y + dirs[i + 1], k - grid[y - 1][x - 1]));\n      seen[y][x] = 0;      \n      return mem[y][x][k] = ans;\n    };        \n    const int ans = dp(n, m, K);\n    return ans >= kInf ? -1 : ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    iven a m * n grid, where each cell is either 0 (empty) or 1 (obstacle). In one step, you can move up, down, left or right from and to an empty cell.…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,278,217,87],"class_list":["post-5966","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-grid","tag-hard","tag-shortest-path","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5966","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5966"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5966\/revisions"}],"predecessor-version":[{"id":5969,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5966\/revisions\/5969"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5966"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5966"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5966"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}