2290 - Minimum Obstacle Removal to Reach Corner

You are given a 0-indexed 2D integer array grid of size m x n. Each cell has one of two values:

• 0 represents an empty cell,

• 1 represents an obstacle that may be removed.

You can move up, down, left, or right from and to an empty cell.

Return the **minimum number of obstacles to remove so you can move from the upper left corner (0, 0) to the lower right corner **(m - 1, n - 1).

  Example 1:

Input: grid = [[0,1,1],[1,1,0],[1,1,0]]
Output: 2
Explanation: We can remove the obstacles at (0, 1) and (0, 2) to create a path from (0, 0) to (2, 2).
It can be shown that we need to remove at least 2 obstacles, so we return 2.
Note that there may be other ways to remove 2 obstacles to create a path.

Example 2:

Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
Output: 0
Explanation: We can move from (0, 0) to (2, 4) without removing any obstacles, so we return 0.

  Constraints:

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 105

• 2 <= m * n <= 105

• grid[i][j] is either 0 or 1.

• grid[0][0] == grid[m - 1][n - 1] == 0

C++

• class Solution {
  public:
      int minimumObstacles(vector<vector<int>>& grid) {
          int m = grid.size(), n = grid[0].size();
          deque<tuple<int, int, int>> q{ {0, 0, 0} };
          bool vis[m][n];
          memset(vis, 0, sizeof vis);
          int dirs[5] = {-1, 0, 1, 0, -1};
          while (1) {
              auto [i, j, k] = q.front();
              q.pop_front();
              if (i == m - 1 && j == n - 1) {
                  return k;
              }
              if (vis[i][j]) {
                  continue;
              }
              vis[i][j] = true;
              for (int h = 0; h < 4; ++h) {
                  int x = i + dirs[h], y = j + dirs[h + 1];
                  if (x >= 0 && x < m && y >= 0 && y < n) {
                      if (grid[x][y] == 0) {
                          q.push_front({x, y, k});
                      } else {
                          q.push_back({x, y, k + 1});
                      }
                  }
              }
          }
      }
  };

JAVA

• class Solution {
      public int minimumObstacles(int[][] grid) {
          int n = grid.length;
          int m = grid[0].length;
          int[][] dirs = new int[][] { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
          Queue<State> q = new PriorityQueue<>((a, b) -> a.removed - b.removed);
          q.add(new State(0, 0, 0));
          boolean[][] visited = new boolean[n][m];
          visited[0][0] = true;
          while (!q.isEmpty()) {
              State state = q.poll();
              if (state.r == n - 1 && state.c == m - 1) {
                  return state.removed;
              }
              for (int[] d : dirs) {
                  int nr = state.r + d[0];
                  int nc = state.c + d[1];
                  if (nr < 0 || nc < 0 || nr == n || nc == m || visited[nr][nc]) {
                      continue;
                  }
                  visited[nr][nc] = true;
                  State next = new State(nr, nc, state.removed);
                  if (grid[nr][nc] == 1) {
                      next.removed++;
                  }
                  q.add(next);
              }
          }
          return -1;
      }
  
      private static class State {
          int r;
          int c;
          int removed;
  
          State(int r, int c, int removed) {
              this.r = r;
              this.c = c;
              this.removed = removed;
          }
      }
  }
  
  ############
  
  class Solution {
      public int minimumObstacles(int[][] grid) {
          int m = grid.length, n = grid[0].length;
          Deque<int[]> q = new ArrayDeque<>();
          q.offer(new int[] {0, 0, 0});
          int[] dirs = {-1, 0, 1, 0, -1};
          boolean[][] vis = new boolean[m][n];
          while (true) {
              var p = q.poll();
              int i = p[0], j = p[1], k = p[2];
              if (i == m - 1 && j == n - 1) {
                  return k;
              }
              if (vis[i][j]) {
                  continue;
              }
              vis[i][j] = true;
              for (int h = 0; h < 4; ++h) {
                  int x = i + dirs[h], y = j + dirs[h + 1];
                  if (x >= 0 && x < m && y >= 0 && y < n) {
                      if (grid[x][y] == 0) {
                          q.offerFirst(new int[] {x, y, k});
                      } else {
                          q.offerLast(new int[] {x, y, k + 1});
                      }
                  }
              }
          }
      }
  }

PYTHON

• from collections import deque
  
  class Solution:
      def minimumObstacles(self, grid):
          m, n = len(grid), len(grid[0])
          q = deque([(0, 0, 0)]) 
          vis = [[False] * n for _ in range(m)]
          dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
  
          while q:
              i, j, k = q.popleft()
              if i == m - 1 and j == n - 1:
                  return k
              if vis[i][j]:
                  continue
              vis[i][j] = True
              for dx, dy in dirs:
                  x, y = i + dx, j + dy
                  if 0 <= x < m and 0 <= y < n:
                      if grid[x][y] == 0:
                          q.appendleft((x, y, k)) 
                      else:
                          q.append((x, y, k + 1))