<p>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:</p>

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

<p>Notice that there could be some signs on the cells of the grid that point outside the grid.</p>

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

<p>You can modify the sign on a cell with <code>cost = 1</code>. You can modify the sign on a cell <strong>one time only</strong>.</p>

<p>Return <em>the minimum cost to make the grid have at least one valid path</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/02/13/grid1.png" style="width: 400px; height: 390px;" />
<pre>
<strong>Input:</strong> grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> You will start at point (0, 0).
The path to (3, 3) is as follows. (0, 0) --&gt; (0, 1) --&gt; (0, 2) --&gt; (0, 3) change the arrow to down with cost = 1 --&gt; (1, 3) --&gt; (1, 2) --&gt; (1, 1) --&gt; (1, 0) change the arrow to down with cost = 1 --&gt; (2, 0) --&gt; (2, 1) --&gt; (2, 2) --&gt; (2, 3) change the arrow to down with cost = 1 --&gt; (3, 3)
The total cost = 3.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/02/13/grid2.png" style="width: 350px; height: 341px;" />
<pre>
<strong>Input:</strong> grid = [[1,1,3],[3,2,2],[1,1,4]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> You can follow the path from (0, 0) to (2, 2).
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/02/13/grid3.png" style="width: 200px; height: 192px;" />
<pre>
<strong>Input:</strong> grid = [[1,2],[4,3]]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 100</code></li>
	<li><code>1 &lt;= grid[i][j] &lt;= 4</code></li>
</ul>

# 1368. Minimum Cost to Make at Least One Valid Path in a Grid

# Given an m x n 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 grid[i][j] can be:

# 1 which means go to the cell to the right. (i.e go from grid[i][j] to grid[i][j + 1])
# 2 which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j - 1])
# 3 which means go to the lower cell. (i.e go from grid[i][j] to grid[i + 1][j])
# 4 which means go to the upper cell. (i.e go from grid[i][j] to grid[i - 1][j])
# 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 (0, 0). A valid path in the grid is a path that starts from the upper left cell (0, 0) and ends at the bottom-right cell (m - 1, n - 1) 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 cost = 1. You can modify the sign on a cell one time only.

# Return the minimum cost to make the grid have at least one valid path.

# Example 1:
# 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:
# 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:
# 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


class Solution:
    # Took me 30 mins, thanks God I needed that
    # No major debugging, just small mistakes in code and I quickly fixed it

    # I overcomplicated the problem initially, then realized it was a bit simpler
    # slightly modified dijkstra
    # I knew I had to use shortest-path upfront because of the topics tab
    # so this gave me an advantage to thinkg about the problem in graph and cost terms

    # It's a Hard problem because Dijkstra isn't easy to code
    # also this requires the trick of adding weight to the edges that "don't exist" requires you to modify and add +1
    # runtime: O(m*n*4(logm*n))??? it seems about right
    # space: m*n of the additional cost table and the visited hashset + space cost of the heap
    def minCost(self, grid: List[List[int]]) -> int:
        return self.dijkstra(grid)

    def dijkstra(self, grid):
        m, n = len(grid), len(grid[0])
        q = [(0, (0, 0))]  # item = cost,(i,j)
        visited = set()
        table = []
        for i in range(len(grid)):
            table.append([])
            for j in range(len(grid[i])):
                table[i].append(math.inf)

        table[0][0] = 0
        while q:
            c = heapq.heappop(q)
            cost, coordinates = c[0], c[1]
            if coordinates not in visited:
                visited.add(coordinates)
                i, j = coordinates[0], coordinates[1]
                if i == m - 1 and j == n - 1:
                    break
                options = [(i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j)]
                #             1        2         3         4
                for k in range(len(options)):
                    oi, oj = options[k][0], options[k][1]
                    if oi < 0 or oj < 0 or oi == m or oj == n:
                        # out-of-bounds edge will be ignored
                        continue
                    edge_cost = 1
                    if k + 1 == grid[i][j]:
                        # if we have our cell pointing to the direction, then the cost of this edge is 0
                        edge_cost = 0
                    total_cost = cost + edge_cost
                    table[oi][oj] = min(table[oi][oj], total_cost)
                    item = (total_cost, (oi, oj))
                    heapq.heappush(q, item)  # having a processed hashset doesn't help

        return table[m - 1][n - 1]


# what if we try to modify each one of them
# 4*n*m * elogv?

# but what if we need to modify many cells? the approach above won't help

# if we traverse assuming we can modify any cell we will potentially not get the minimum cost to have a valid path
# we will get a path and the cost to make that path possible, it might not be the minimum cost possible

# we want the minimum cost to make path valid from src to tgt
# we always assume we can modify all 4 possible cells
# if we need to modify to get to a cell we add that to the cost of the cell
# if we run dijkstra, with hashset to keep visited
# if next cell is out of bounds we don't even consider it (filter out)

465