leetcode 1368

问题

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:

img

1
2
3
4
5
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:

img

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

Example 3:

img

1
2
Input: grid = [[1,2],[4,3]]
Output: 1

Example 4:

1
2
Input: grid = [[2,2,2],[2,2,2]]
Output: 3

Example 5:

1
2
Input: grid = [[4]]
Output: 0

Constraints:

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

分析

方案一：使用优先队列进行图的搜索，每个节点在出站时被确定所需要的花费。时间复杂度 $O(NMlogNM)$，空间复杂度 $O(NM)$ 。

方案二：使用BFS+DFS，BFS用来按照cost从小到大依次访问节点，DFS用来在层级内进行穿梭，搜索同一层的节点。时间复杂度 $O(NM)$，空间复杂度 $O(NM)$ 。

代码1

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
// 优先队列
class Solution {
public:
    vector<vector<int>> dirs = {{0, 0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = m==0? 0: grid[0].size();
        vector<vector<bool>> v(m, vector<bool>(n, false));
        priority_queue<pair<int,pair<int, int>>> q;
        // 默认为大根堆，第一维用来保存负值使其成为“小根堆”
        q.push({0, {0, 0}});
        while (q.size()) {
            int level = -(q.top().first);
            int x = (q.top().second.first);
            int y = (q.top().second.second);
            q.pop();
            
            if (v[x][y] == true) continue;
            v[x][y] = true;
            if (x == m-1 && y == n-1)
                return level;

            for (int i = 1; i <= 4; ++i) {
                int x_ = x+dirs[i][0];
                int y_ = y+dirs[i][1];
                if (x_ < 0 || x_ >= m || y_ < 0 || y_ >= n)
                    continue;
                int newLevel = grid[x][y] == i? level: level+1;
                q.push(make_pair(-newLevel, make_pair(x_, y_)));
            }
        }
        return -1;
    }
};

代码2

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
// BFS+DFS
class Solution {
public:
    int dirs[5][2] = {{0,0}, {0,1}, {0,-1}, {1,0}, {-1,0}};
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = m==0? 0: grid[0].size();
        vector<vector<int>> cost(m, vector<int>(n, -1));
        queue<pair<int, int>> q;
        dfs(0, 0, 0, cost, grid, q);
        int level = 0;
        while (q.size() > 0) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (int i = 1; i <= 4; ++i) {
                int x_ = x+dirs[i][0];
                int y_ = y+dirs[i][1];
                dfs(x_ , y_, cost[x][y]+1, cost, grid, q);
            }
        }
        return cost[m-1][n-1];
    }
	// dfs搜索同一层的元素
    void dfs(int x, int y, int c, 
        vector<vector<int>>& cost,
        vector<vector<int>>& grid, 
        queue<pair<int, int>>& q)
    {
        int m = grid.size(), n = grid[0].size();
        if (x<0 || x>=m || y<0 || y>=n || cost[x][y] != -1)
            return;
        cost[x][y] = c;
        q.push(make_pair(x, y));
        int d = grid[x][y];
        dfs(x+dirs[d][0], y+dirs[d][1], c, cost, grid, q);
    }
};