Given a m x ngrid. 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]togrid[i][j + 1]) - 2 which means go to the cell to the left. (i.e go from
grid[i][j]togrid[i][j - 1]) - 3 which means go to the lower cell. (i.e go from
grid[i][j]togrid[i + 1][j]) - 4 which means go to the upper cell. (i.e go from
grid[i][j]togrid[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.lengthn == grid[i].length1 <= m, n <= 100
Solution 1: Lazy BFS (fake DP)
dp[i][j] := min steps to reach (i, j)
Time complexity: O((m+n)*m*n)
Space complexity: O(m*n)
C++
|
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 |
// Author: Huahua class Solution { public: int minCost(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); vector<vector<int>> dp(m, vector<int>(n, INT_MAX / 2)); dp[0][0] = 0; auto solve = [&](int x, int y) { int& v = dp[y][x]; if (x > 0) v = min(v, dp[y][x - 1] + (grid[y][x - 1] != 1)); if (y > 0) v = min(v, dp[y - 1][x] + (grid[y - 1][x] != 3)); if (x < n - 1) v = min(v, dp[y][x + 1] + (grid[y][x + 1] != 2)); if (y < m - 1) v = min(v, dp[y + 1][x] + (grid[y + 1][x] != 4)); }; // At most m + n steps to propagate the results to (m - 1, n -1). for (int k = 0; k <= (m + n); ++k) { for (int y = 0; y < m; ++y) for (int x = 0; x < n; ++x) solve(x, y); for (int y = m - 1; y >= 0; --y) for (int x = n - 1; x >= 0; --x) solve(x, y); } return dp[m - 1][n - 1]; } }; |
C++
|
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 |
// Author: Huahua, 88 ms / 22.9 MB class Solution { public: int minCost(vector<vector<int>>& grid) { const int m = grid.size(); const int n = grid[0].size(); vector<vector<int>> dp(m, vector<int>(n, INT_MAX / 2)); dp[0][0] = 0; while (true) { auto prev(dp); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { if (i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + (grid[i - 1][j] != 3)); if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + (grid[i][j - 1] != 1)); } for (int i = m - 1; i >= 0; --i) for (int j = n - 1; j >= 0; --j) { if (i != m - 1) dp[i][j] = min(dp[i][j], dp[i + 1][j] + (grid[i + 1][j] != 4)); if (j != n - 1) dp[i][j] = min(dp[i][j], dp[i][j + 1] + (grid[i][j + 1] != 2)); } if (prev == dp) break; // optimal solution obtained. } return dp[m - 1][n - 1]; } }; |
Solution 2: 0-1 BFS
Time complexity: O(m*n)
Space complexity: O(m*n)
C++
|
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 |
// Author: Huahua class Solution { public: int minCost(vector<vector<int>>& grid) { const int m = grid.size(); const int n = grid[0].size(); deque<pair<int, int>> q{{0, 0}}; vector<char> seen(m * n); vector<vector<int>> dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; while (!q.empty()) { auto [p, cost] = q.front(); q.pop_front(); int x = p % n, y = p / n; if (x == n - 1 && y == m - 1) return cost; if (seen[p]++) continue; for (int i = 0; i < 4; ++i) { int tx = x + dirs[i][0], ty = y + dirs[i][1]; int tp = ty * n + tx; if (tx < 0 || ty < 0 || tx >= n || ty >= m || seen[tp]) continue; if (grid[y][x] == i + 1) q.emplace_front(tp, cost); else q.emplace_back(tp, cost + 1); } } return -1; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment