Shortest Path in a Grid with Obstacles Elimination

Explore Other Solutions

Problem Description

Imagine you’re on a quest to find the shortest path through a grid, but wait! There are obstacles in your way. It’s like trying to navigate through a crowded mall during a holiday sale—everyone’s in your way, and you can only shove a few people aside (or in this case, eliminate a few obstacles). The goal is to get from the top-left corner of the grid to the bottom-right corner while eliminating a limited number of obstacles.

In this problem, you are given a grid where 0 represents an empty cell and 1 represents an obstacle. You can eliminate up to k obstacles to find the shortest path. If you think this sounds easy, just remember that life is full of unexpected roadblocks—like that time you tried to take a shortcut through a construction site!

Code Solution


class Solution {
  public int shortestPath(int[][] grid, int k) {
    record T(int i, int j, int eliminate) {}
    final int m = grid.length;
    final int n = grid[0].length;
    if (m == 1 && n == 1)
      return 0;

    final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    Queue q = new ArrayDeque<>(List.of(new T(0, 0, k)));
    boolean[][][] seen = new boolean[m][n][k + 1];
    seen[0][0][k] = true;

    for (int step = 1; !q.isEmpty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        final int i = q.peek().i;
        final int j = q.peek().j;
        final int eliminate = q.poll().eliminate;
        for (int l = 0; l < 4; ++l) {
          final int x = i + dirs[l][0];
          final int y = j + dirs[l][1];
          if (x < 0 || x == m || y < 0 || y == n)
            continue;
          if (x == m - 1 && y == n - 1)
            return step;
          if (grid[x][y] == 1 && eliminate == 0)
            continue;
          final int newEliminate = eliminate - grid[x][y];
          if (seen[x][y][newEliminate])
            continue;
          q.offer(new T(x, y, newEliminate));
          seen[x][y][newEliminate] = true;
        }
      }

    return -1;
  }
}

Approach Explanation

The approach used in this solution is a breadth-first search (BFS) algorithm. The algorithm explores all possible paths from the starting point (top-left corner) to the destination (bottom-right corner) while keeping track of the number of obstacles eliminated. The BFS ensures that we explore the shortest paths first, and we use a queue to manage the cells to be explored.

Initialization: We create a queue to hold the current position and the number of obstacles we can still eliminate. We also maintain a 3D boolean array to track visited states.
BFS Loop: For each step, we explore all four possible directions (up, down, left, right). If we reach the destination, we return the number of steps taken.
Obstacle Handling: If we encounter an obstacle, we check if we can eliminate it. If we can, we continue exploring from that cell.
Termination: If we exhaust all possibilities without reaching the destination, we return -1.

Time and Space Complexity

Time Complexity: O(m * n * k), where m is the number of rows, n is the number of columns, and k is the maximum number of obstacles that can be eliminated. This is because we may need to explore each cell with each possible number of eliminations.

Space Complexity: O(m * n * k) for the visited states array and the queue used in BFS.

Real-World Example

Think of this problem like trying to navigate through a busy airport. You start at the entrance (top-left corner) and need to reach your gate (bottom-right corner). Along the way, there are obstacles like slow-moving travelers (obstacles) and security checks (eliminations). You can only push through a limited number of people (k obstacles) to make it to your gate on time. The challenge is to find the quickest route while managing the chaos around you!