 # CHAAT7 - Editorial

Contest
Tester: Hareesh

Easy

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:

1. The cell that can be reached by following the direction [say L]
2. 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
q.popleft()
ci, cj = t//n, t % n
if t not in vis:
res = t
if ci == m-1 and cj == n-1:
return res
for i, dv in enumerate(dirp):
x, y = ci+dv, cj+dv
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]) if i == dirv.index(
grid[ci][cj]) else q.append([p, t+1])
return res

m, n = map(int, input().split())
print(minCost([input().split() for i in range(m)], m, n))

``````

can anyone provide c++ 0/1 bfs solution for it , mine is not passing all the test cases

Hey, since this is a private contest, please contact the organizers of the contest for the solution.