CHAAT7 - Editorial

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:

  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[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))