In an n*n grid, there is a snake that spans 2 cells and starts moving from the top left corner at (0, 0) and (0, 1). The grid has empty cells represented by zeros and blocked cells represented by ones. The snake wants to reach the lower right corner at (n-1, n-2) and (n-1, n-1).
In one move the snake can:
- Move one cell to the right if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
- Move down one cell if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
- Rotate clockwise if it’s in a horizontal position and the two cells under it are both empty. In that case the snake moves from
(r, c)and(r, c+1)to(r, c)and(r+1, c). - Rotate counterclockwise if it’s in a vertical position and the two cells to its right are both empty. In that case the snake moves from
(r, c)and(r+1, c)to(r, c)and(r, c+1).
Return the minimum number of moves to reach the target.
If there is no way to reach the target, return -1.
Example 1:
Input: grid = [[0,0,0,0,0,1],
[1,1,0,0,1,0],
[0,0,0,0,1,1],
[0,0,1,0,1,0],
[0,1,1,0,0,0],
[0,1,1,0,0,0]]
Output: 11
Explanation:
One possible solution is [right, right, rotate clockwise, right, down, down, down, down, rotate counterclockwise, right, down].
Example 2:
Input: grid = [[0,0,1,1,1,1], [0,0,0,0,1,1], [1,1,0,0,0,1], [1,1,1,0,0,1], [1,1,1,0,0,1], [1,1,1,0,0,0]] Output: 9
Constraints:
2 <= n <= 1000 <= grid[i][j] <= 1- It is guaranteed that the snake starts at empty cells.
Solution1: BFS
Time complexity: O(n^2)
Space complexity: O(n^2)
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
// Author: Huahua, 48 ms, 18.1 MB class Solution { public: inline int pos(int x, int y) { return y * 100 + x; } inline int encode(int p1, int p2) { return (p1 << 16) | p2; } int minimumMoves(vector<vector<int>>& grid) { int n = grid.size(); queue<pair<int, int>> q; unordered_set<int> seen; q.push({pos(0, 0), pos(1, 0)}); // tail, head seen.insert(encode(pos(0, 0), pos(1, 0))); int steps = 0; auto valid = [&](int x, int y) { bool v = x >= 0 && x < n && y >= 0 && y < n && !grid[y][x]; return v; }; while (!q.empty()) { int size = q.size(); while (size--) { auto p = q.front(); q.pop(); int y0 = p.first / 100; int x0 = p.first % 100; int y1 = p.second / 100; int x1 = p.second % 100; if (x0 == n - 2 && y0 == n - 1 && x1 == n - 1 && y1 == n - 1) { return steps; } bool h = y0 == y1; for (int i = 0; i < 3; ++i) { int tx0 = x0; int ty0 = y0; int tx1 = x1; int ty1 = y1; int rx = x0; int ry = y0; switch (i) { case 0: // down ++ty0; ++ty1; break; case 1: // right ++tx0; ++tx1; break; case 2: // rotate ++rx; ++ry; if (h) { // clockwise --tx1; ++ty1; } else { // counterclockwise ++tx1; --ty1; } break; } if (!valid(tx0, ty0) || !valid(tx1, ty1) || !valid(rx, ry)) continue; int key = encode(pos(tx0, ty0), pos(tx1, ty1)); if (seen.count(key)) continue; seen.insert(key); q.push({pos(tx0, ty0), pos(tx1, ty1)}); } } ++steps; } return -1; } }; |
Solution 2: DP
dp[i][j].first = min steps to reach i,j (tail pos) facing right
dp[i][j].second = min steps to reach i, j (tail pos) facing down
ans = dp[n][n-1].first
Time complexity: O(n^2)
Space complexity: O(n^2)
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, 16 ms, 12.1MB class Solution { public: int minimumMoves(vector<vector<int>>& grid) { constexpr int kInf = 1e9; const int n = grid.size(); vector<vector<pair<int, int>>> dp(n + 1, vector<pair<int, int>>(n + 1, {kInf, kInf})); dp[0][1].first = dp[1][0].first = -1; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) { bool h = false; bool v = false; if (!grid[i - 1][j - 1] && j < n && !grid[i - 1][j]) { dp[i][j].first = min(dp[i - 1][j].first, dp[i][j - 1].first) + 1; h = true; } if (!grid[i - 1][j - 1] && i < n && !grid[i][j - 1]) { dp[i][j].second = min(dp[i - 1][j].second, dp[i][j - 1].second) + 1; v = true; } if (v && j < n && !grid[i][j]) dp[i][j].second = min(dp[i][j].second, dp[i][j].first + 1); if (h && i < n && !grid[i][j]) dp[i][j].first = min(dp[i][j].first, dp[i][j].second + 1); } return dp[n][n - 1].first >= kInf ? -1 : dp[n][n - 1].first; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment