PROBLEM LINK
Contest
Author: Adithi Narayan
Tester: Hareesh
Editorialist: Adithi Narayan
DIFFICULTY
Easy
PREREQUISITES
BFS
PROBLEM
Given a grid where each cell holds a direction [T,L,D,R], find the path from top left to bottom right given that you can either move in the direction specified in the cell or pay a penalty to move in some other direction. (Note that for a cell in the grid the change of direction can only be done once.)
EXPLANATION
We have to reach (m - 1, n - 1) from (0, 0) with a path that minimizes the penalty paid. For each cell, you have 2 choices:
- The cell that can be reached by following the direction [say L]
- Three other cells that can be reached via the other directions [say T, D and R]
Thus we have 1 edge of weight 0 and 3 edges of weight 1 [as we incur a penalty]. The problem now reduces to a simple path finding problem. The default choice of algorithm to solve this would be Dijkstra’s but it’s time complexity is O(E + V log V).
However, if we notice the constraints we can see that the edges are binary weighted. We can either follow the directions to reach the cell with cost 0 or change the direction and incur a penalty of 1. So, we can use a more efficient algorithm: 0-1 BFS which uses a deque and has the time complexity of O(E + V)
In the normal BFS, we do the following changes:
- If the adjacent cell has a cost of 0 [following direction], append it to the left of the queue else append the cell to the right
- Always pop the node at the left
This makes sure that we visit all nodes of a lower cost difference before moving on to the ones with a higher cost difference.
Setter's Solution
from collections import deque
def minCost(grid, m, n):
q = deque([[0, 0]])
dirp = [[-1, 0], [1, 0], [0, -1], [0, 1]]
dirv = ['T', 'D', 'L', 'R']
vis = set([])
res = 0
while q:
t = q[0]
q.popleft()
ci, cj = t[0]//n, t[0] % n
if t[0] not in vis:
res = t[1]
vis.add(t[0])
if ci == m-1 and cj == n-1:
return res
for i, dv in enumerate(dirp):
x, y = ci+dv[0], cj+dv[1]
p = x*n + y
if x < 0 or x >= m or y < 0 or y >= n or (p in vis):
continue
q.appendleft([p, t[1]]) if i == dirv.index(
grid[ci][cj]) else q.append([p, t[1]+1])
return res
m, n = map(int, input().split())
print(minCost([input().split() for i in range(m)], m, n))