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

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.

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

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

## 分析

### 思路2 DFS+BFS

TLE之后呢，我就看了lee神的解答。原来这道题的本质就是求矩阵两点最短路径的变体。矩阵中两点距离最短，经典解法就是Dijkstra，正常来讲我们应该先写出Dijkstra的解法，然后优化得到DFS+BFS的解法。但是其实两者的思路是相通的。

Dijkstra的思想是维护一个最短路径表。而对于DFS+BFS来说：

1. 我们从(0,0)开始，首先根据箭头指示，DFS来将所有cost=0的点都遍历一遍，在表dp[m][n]中记录cost=0的点，并将这些点保存在用来DFS的队列queue中。
2. 遍历queue，对于每一个cost=0的点都进行其他三个方向的cost+1的遍历，此时将dp中cost=1的点都刷了一遍。
3. 重复上述步骤，于dp表来讲，我们一步步将cost=0,1,2…的点都填入到表中，从而得到从(0,0)到每个点的最短距离。

class Solution {
private int[][] dir = new int[][]{{0 ,1}, {0, -1}, {1, 0}, {-1, 0}};

public int minCost(int[][] grid) {
int m = grid.length, n = grid[0].length;
int cost = 0;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++)
Arrays.fill(dp[i], Integer.MAX_VALUE);

dfs(grid, dp, 0, 0, 0, queue); // 将cost=0的点更新
while (!queue.isEmpty()) {
cost++;
for (int i = queue.size(); i > 0; i--) {
int[] top = queue.poll();
int r = top[0], c = top[1];
for (int j = 0; j < 4; j++)
dfs(grid, dp, r + dir[j][0], c + dir[j][1], cost, queue);
}
}
return dp[m - 1][n - 1];
}

private void dfs(int[][] grid, int[][] dp, int r, int c, int cost, Queue<int[]> queue) {
int m = grid.length, n = grid[0].length;
if (r < 0 || r >= m || c < 0 || c >= n || dp[r][c] != Integer.MAX_VALUE)
return;
queue.offer(new int[]{r, c});
dp[r][c] = cost;
int dirIndex = grid[r][c] - 1;
dfs(grid, dp, r + dir[dirIndex][0], c + dir[dirIndex][1], cost, queue);
}
}

lee215的解答