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

Description

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

Solution

BFS

Similar to 1293. Shortest Path in a Grid with Obstacles Elimination, we start from the left upper corner, and BFS. If a cell is visited before but we have higher cost, we could re-visit it.

To optimize, we could put any 0 cost to one end of the queue, and 1 cost to the other end of the queue.

Time complexity: $o(m\ast n)$
Space complexity: $o(m\ast n)$

Code

BFS

class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        queue = collections.deque([(0, 0, 0)])
        visited = {}
        res = m * n
        directions = [1,2,3,4]
        while queue:
            x, y, cost = queue.popleft()
            if visited.get((x, y), m * n) <= cost:
                continue
            visited[(x, y)] = cost
            if x == m - 1 and y == n - 1:
                res = min(res, cost)
                continue
            for each_direction in directions:
                if each_direction == 1 and y + 1 < n:
                    queue.append((x, y + 1, cost + (1 if grid[x][y] != 1 else 0)))
                elif each_direction == 2 and y - 1 >= 0:
                    queue.append((x, y - 1, cost + (1 if grid[x][y] != 2 else 0)))
                elif each_direction == 3 and x + 1 < m:
                    queue.append((x + 1, y, cost + (1 if grid[x][y] != 3 else 0)))
                elif each_direction == 4 and x - 1 >= 0:
                    queue.append((x - 1, y, cost + (1 if grid[x][y] != 4 else 0)))
        return res

原文地址：https://blog.csdn.net/sinat_41679123/article/details/145220281

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！