## 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))
```