---
tags: Algorithm
---
# Leet Code 1293 Shortest Path in a Grid with Obstacles Elimination

contributed by: `ngokchaoho`

Questions: https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

Recently, I start practising algorithm again. I pick up a book called プログラミングコンテストチャレンジブック [第2版] and reached its BFS (breath first search) section, it introduced a classic problem finding short path for maze. BFS is often implemented through Queue. For python user, you can use `queue` module.

import queue
que = queue.Queue()

BFS complexity is often O(number of way to transit * number of possible states)

After that, I start searching online for similar question and comes across this one from leet code. The only difference is it now has obsstacles elimination.

From a first look to me, it is just more states, I can treat it as a normal BFS only that apart from the grid's coordinates, the amount of elimination allowed when reaching that grid is also a part of the state.

>Constraints:
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

Hence, I first come up with this, which is just BFS without cutting branch. It is O (m * n * k) and since k can be super large, it gets exceeding time limit error. Thanks to BFS, every element in short_len is the shortest path for a specific state.

import queue
from collections import defaultdict
class Solution:
    def shortestPath(self, maze: List[List[int]], k: int) -> int:
        n = len(maze)
        m = len(maze[0])
        start=(0,0,k)
        end=(n-1,m-1)
        if end==(0,0):
            return 0
        que = queue.Queue()
        que.put(start)
        short_len = defaultdict(lambda:1600)
        short_len[start] = 0
        while que.qsize():
            current_step = que.get()
            next_step = []
            if current_step[0:2]==end:
                return short_len[current_step]
            if current_step[0] - 1 >= 0:
                next_step.append((current_step[0]-1,current_step[1],current_step[2]))
            if current_step[1] - 1 >= 0:
                next_step.append((current_step[0],current_step[1]-1,current_step[2]))
            if current_step[0] + 1 < n:
                next_step.append((current_step[0]+1,current_step[1],current_step[2]))
            if current_step[1] + 1 < m:
                next_step.append((current_step[0],current_step[1]+1,current_step[2]))

            for _ in next_step:

                if maze[_[0]][_[1]]!=1:
                    best = short_len[_]
                    if best > short_len[current_step] + 1:
                        short_len[_] = short_len[current_step] + 1
                        que.put(_)
                elif current_step[2]>=1:
                    best = short_len[(_[0],_[1],_[2]-1)]
                    if best > short_len[current_step] + 1:
                        short_len[(_[0],_[1],_[2]-1)] = short_len[current_step] + 1
                        new_stats = (_[0],_[1],_[2]-1)
                        que.put(new_stats)

        return -1

My answer that got accepted is the following, which is just cutting some branch that is deemed to not going to impact the path to the goal's shortest path.

You see a simple BFS is trying to reach all the state. My implementation of the state is (i,j,k) i.e. row i, column j, k remaining balance removing obstacles. Hence, if the next step is to x,y with p passing power in balance, I am going to ask what is the current best shortest path to x,y with p or more passing power in balance, if the next step is no better than the current best then it is deemed to be useless branch as we are guaranteed to have equivalent or better choice already, I don't need to put it into the queue and suffer from all its follow up.

Reminder: This is not a very smart solution as I used for-loop to search for the `best` current shortest path with comparable balance or more all the way up to balance of k as I don't know how many balance is possible and k can be large.

Hence, I memorise what is the current best balance to that grid.

import queue
from collections import defaultdict
class Solution:
    def shortestPath(self, maze: List[List[int]], k: int) -> int:
        n = len(maze)
        m = len(maze[0])
        start=(0,0,k)
        end=(n-1,m-1)
        if end==(0,0):
            return 0
        que = queue.Queue()
        que.put(start)
        short_len = defaultdict(lambda:1600)
        max_k = defaultdict(int)
        short_len[start] = 0
        max_k[(0,0)] = k
        while que.qsize():
            current_step = que.get()
            next_step = []
            if current_step[0] == n-1 and current_step[1] == m-1:
                return short_len[current_step]
            if current_step[0] - 1 >= 0:
                next_step.append((current_step[0]-1,current_step[1],current_step[2]))
            if current_step[1] - 1 >= 0:
                next_step.append((current_step[0],current_step[1]-1,current_step[2]))
            if current_step[0] + 1 < n:
                next_step.append((current_step[0]+1,current_step[1],current_step[2]))
            if current_step[1] + 1 < m:
                next_step.append((current_step[0],current_step[1]+1,current_step[2]))

            for _ in next_step:

                if maze[_[0]][_[1]]!=1 :
                    if _[2] < max_k[(_[0],_[1])]+1:
                        best = min([short_len[(_[0],_[1],i)] for i in range(_[2],max_k[(_[0],_[1])]+1)])
                    else:
                        best = short_len[_]
                    if best > short_len[current_step] + 1:
                        if _[2] > max_k[(_[0],_[1])]:
                            max_k[(_[0],_[1])] = _[2]
                        short_len[_] = short_len[current_step] + 1
                        que.put(_)
                elif current_step[2]>=1:
                    if _[2] < max_k[(_[0],_[1])]+1:
                        best = min([short_len[(_[0],_[1],i)] for i in range(_[2]-1,max_k[(_[0],_[1])]+1)])
                    else:
                        best = short_len[(_[0],_[1],_[2]-1)]
                    if best > short_len[current_step] + 1:
                        if _[2]-1 > max_k[(_[0],_[1])]:
                            max_k[(_[0],_[1])] = _[2]-1
                        short_len[(_[0],_[1],_[2]-1)] = short_len[current_step] + 1
                        new_stats = (_[0],_[1],_[2]-1)
                        que.put(new_stats)
        return -1

result:

Runtime: 944 ms, faster than 17.99% of Python3 online submissions for Shortest Path in a Grid with Obstacles Elimination.
Memory Usage: 16.9 MB, less than 52.30% of Python3 online submissions for Shortest Path in a Grid with Obstacles Elimination.