Given a 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 invalid signs on the cells of the grid which points outside the grid.
You will initially start at the upper left cell (0,0). A valid path in the grid is a path which 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 doesn't 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.

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.

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

Input: grid = [[1,2],[4,3]]
Output: 1
Example 4:
Input: grid = [[2,2,2],[2,2,2]]
Output: 3
Example 5:
Input: grid = [[4]]
Output: 0
 
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:
    # 按移动花费来 bfs 遍历图
    def minCost(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        # 移动方向数组，index+1 = 题目里的编号
        dirs = [(0,1), (0,-1),(1,0),(-1,0)]
        visited = set()
        # 为了简单一点没有用队列，使用了dict+list，key 为 cost，value 为下标组成的list
        # 表示从起始点到该list的中的点的花费为key值
        costs = {0:[(0,0)]} 
        cost = 0
        # 按 cost 遍历，由于遍历是 costs 中的 cost 会增多，不写成 for cost in costs
        while cost in costs:
            for i,j in costs[cost]:
                # 目标点没有访问过
                if (i,j) not in visited:
                    visited.add((i,j))
                    # 到达终点结束
                    if i == m-1 and j == n-1:
                        return cost
                    # 求四个方向的消耗，并加入costs
                    for val, d in enumerate(dirs):
                        x = i + d[0]
                        y = j + d[1]
                        # 目标点合法，且没有访问过
                        if 0<=x<m and 0<=j<n and (x,y) not in visited:
                            # 如果和i，j的方向一致则cost不变，否则加1
                            next_cost = cost + (0 if val+1 == grid[i][j] else 1)
                            # 加入 costs
                            if next_cost not in costs:
                                costs[next_cost] = []
                            costs[next_cost].append((x,y))
            cost += 1
        return 0