Given an <code>m x n</code> grid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of <code>grid[i][j]</code> can be:<ul>
<li><code>1</code> which means go to the cell to the right. (i.e go from <code>grid[i][j]</code> to <code>grid[i][j + 1]</code>)</li>
<li><code>2</code> which means go to the cell to the left. (i.e go from <code>grid[i][j]</code> to <code>grid[i][j - 1]</code>)</li>
<li><code>3</code> which means go to the lower cell. (i.e go from <code>grid[i][j]</code> to <code>grid[i + 1][j]</code>)</li>
<li><code>4</code> which means go to the upper cell. (i.e go from <code>grid[i][j]</code> to <code>grid[i - 1][j]</code>)</li>
</ul>Notice that there could be some signs on the cells of the grid that point outside the grid.You will initially start at the upper left cell <code>(0, 0)</code>. A valid path in the grid is a path that starts from the upper left cell <code>(0, 0)</code> and ends at the bottom-right cell <code>(m - 1, n - 1)</code> following the signs on the grid. The valid path does not have to be the shortest.You can modify the sign on a cell with <strong>cost = 1</strong>. You can modify the sign on a cell <strong>one time only</strong>.Return the <em>minimum cost to make the grid have at least one <strong>valid path</strong></em>.
Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]Output: 3Explanation: You will start at point (0, 0).The path to (3, 3) is as follows. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) change the arrow to down with cost = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) change the arrow to down with cost = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) change the arrow to down with cost = 1 --> (3, 3)The total cost = 3.
Input: grid = [[1,1,3],[3,2,2],[1,1,4]]Output: 0Explanation: You can follow the path from (0, 0) to (2, 2).
from collections import dequeclass Solution: # Time: O(m * n) # Space: O(m * n) def min_cost(self, grid: list[list[int]]) -> int: # 0-1 BFS: follow the cell's own sign with cost 0, any other # direction with cost 1. dirs = {1: (0, 1), 2: (0, -1), 3: (1, 0), 4: (-1, 0)} m, n = len(grid), len(grid[0]) inf_cost = 10**9 dist = [[inf_cost] * n for _ in range(m)] dist[0][0] = 0 dq: deque[tuple[int, int, int]] = deque([(0, 0, 0)]) while dq: d, i, j = dq.popleft() if d > dist[i][j]: continue for s, (di, dj) in dirs.items(): ni, nj = i + di, j + dj if 0 <= ni < m and 0 <= nj < n: nd = d if grid[i][j] == s else d + 1 if nd < dist[ni][nj]: dist[ni][nj] = nd if nd == d: dq.appendleft((nd, ni, nj)) else: dq.append((nd, ni, nj)) return dist[m - 1][n - 1]
