> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Minimum Cost to Make at Least One Valid Path

> Tested Python solution for LeetCode 1368 with 24 pytest cases. Generate a practice environment with lcpy.

LeetCode 1368, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Breadth-First Search](/catalog/topics/breadth-first-search), [Graph](/catalog/topics/graph), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue), [Matrix](/catalog/topics/matrix), [Shortest Path](/catalog/topics/shortest-path). [View on LeetCode](https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/description/).

Generate this problem as a practice environment: tested reference solution, 24 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1368   # by problem number
lcpy gen -s minimum_cost_to_make_at_least_one_valid_path_in_a_grid   # by problem name
```

## Problem

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>.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2020/02/13/grid1.png)

```
Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3
Explanation: 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.
```

![Example 2](https://assets.leetcode.com/uploads/2020/02/13/grid2.png)

```
Input: grid = [[1,1,3],[3,2,2],[1,1,4]]
Output: 0
Explanation: You can follow the path from (0, 0) to (2, 2).
```

![Example 3](https://assets.leetcode.com/uploads/2020/02/13/grid3.png)

```
Input: grid = [[1,2],[4,3]]
Output: 1
```

### Constraints

* m == grid.length
* n == grid\[i].length
* 1 \<= m, n \<= 100
* 1 \<= grid\[i]\[j] \<= 4

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_cost_to_make_at_least_one_valid_path_in_a_grid/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_cost_to_make_at_least_one_valid_path_in_a_grid/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import deque


class 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]
```

## Complexity

| Time | Space |
| - | - |
| O(m \* n) | O(m \* n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.