leetcode1368-Minimum Cost to Make at Least One Valid Path in a Grid

1、题目大意

给定m*n个格子，grid[m][n]，对于每个格子grid[i][j]值为1~4

  • 1代表往右走，即下一个格子为grid[i][j + 1]
  • 2代表往左走，即下一个格子为grid[i][j - 1]
  • 3代表往下走，即下一个格子为grid[i + 1][j]
  • 4代表往上走，即下一个格子为grid[i - 1][j]

问，从grid[0][0]走到grid[m - 1][n - 1]最少需要改变多少个格子的方向。

img

这个例子需要至少改变三个格子的方向，如(0,0)，(1,0)，(2,3)这三个格子的方向。

范围：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100

2、思路

分析此题，要求从左上角走到左下角，那么需要改变的格子数量最多不会超过m+n个。

每个格子可能从四个方向过来最短，那么对每个格子求从(0,0)位置到自己位置的最短路，再不断更新最小值。

通过bfs，首先将(0,0)位置加入队列，再更新相邻格子的最小值即可，直到无法更新即求得到(m-1,n-1)位置的最小值。

3、代码

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
class Solution {
    public int minCost(int[][] grid) {
        final int INF = 1000; 
        //四个方向，这里左、右、下、上下标大小与题目方向1、2、3、4大小均相差1，方便进行运算
        int dx[] = {0, 0, 1, -1}; 
        int dy[] = {1, -1, 0, 0};
        int res = 0;
        int m = grid.length;
        int n = grid[0].length;
        int dis[][] = new int[m][n];
        //初始化距离
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dis[i][j] = INF;
            }
        }
        dis[0][0] = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        while (!queue.isEmpty()) {
            int[] p = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = p[0] + dx[i];
                int ny = p[1] + dy[i];
                if(nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    int d = 0;
                    //判断x=p[0],y=p[1]到nx,ny位置是否需要改变方向
                    //grid[p[0]][p[1]] - i 为1则说明方向一致，不需要改变
                    if(grid[p[0]][p[1]] - i != 1) d = 1;
                    if(dis[nx][ny] > dis[p[0]][p[1]] + d) {
                        dis[nx][ny] = dis[p[0]][p[1]] + d;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
        }
        return dis[m - 1][n - 1];
    }
}

最后更新： 2020年07月14日 21:11

原始链接： http://tanruidd.github.io/2020/07/14/leetcode-1368/