0 like 0 dislike
777 views
| 777 views

0 like 0 dislike

Question 1:
Aladdin positioned on (0, 0) wants to reach Jasmine at (r-1, c-1). He has k coins. We are given with a grid of cities where each city either charges 1 coin or 0 coins. Aladdin can move either horizontally or vertically one step in this grid to reach Jasmine. Find out the minimum steps taken to reach Jasmine.

``````Ex:
r = 5, c = 3, k = 1

0 0 1
1 0 1
1 0 1
0 1 0
0 0 0

Ans: 6``````
by Expert (46,090 points)
0 like 0 dislike

# Python # Approach : Heap

``````import heapq
from typing import List

def solve(grid:List[List[int]], k:int)->int:
rows, cols = len(grid), len(grid[0])
directions = [[0,1],[0,-1],[1,0],[-1,0]]

pq = ([(0,k,0,0)])      # steps,remainK,r,c

while pq:
steps,remK,r,c = heapq.heappop(pq)
if r == rows-1 and c == cols-1 :
return steps
if remK < 0:
continue
for dr,dc in directions :
newR,newC = r+dr, c+dc
if newR<0 or newR>=rows or newC<0 or newC>=cols :
continue
heapq.heappush(pq,(steps+1,remK-grid[newR][newC],newR,newC))

print(solve([[0 ,0, 1], [1, 0, 1],[1, 0, 1],[0 ,1,0],[0, 0, 0]],1))``````
by Expert (46,090 points)