aboutsummaryrefslogtreecommitdiff
path: root/min_cost_valid_path.py
blob: 713ec86581c65b646be5aae68620343977341c50 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 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 shhould visit if you are currently in this cell. 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 uppper left cell '(0, 0)' and ends at the
bbbottom right cell '(m - 1, n - 1)' following the signs on the grid. the
valid path does not have to bbe the shortest. return the minimum cost to make
the grid have at least one valid path
"""


class Solution(object):
    def minCost(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        n, m, inf, k = len(grid), len(grid[0]), 10**9, 0
        dp, bfs = [[inf] * m for i in range(n)], []
        dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]

        def dfs(x, y):
            if not (0 <= x < n and 0 <= y < m and dp[x][y] == inf):
                return
            dp[x][y] = k
            bfs.append([x, y])
            dfs(x + dir[grid[x][y] - 1][0], y + dir[grid[x][y] - 1][1])

        dfs(0, 0)
        while bfs:
            k += 1
            bfs, bfs2 = [], bfs
            [dfs(x + i, y + j) for x, y in bfs2 for i, j in dir]
        return dp[-1][-1]


if __name__ == "__main__":
    obj = Solution()
    print(obj.minCost(grid=[[1, 1, 1, 1], [2, 2, 2, 2], [1, 1, 1, 1], [2, 2, 2, 2]]))
    print(obj.minCost(grid=[[1, 1, 3], [3, 2, 2], [1, 1, 4]]))
    print(obj.minCost(grid=[[1, 2], [4, 3]]))