Storekeeper is a game in which the player pushes boxes around in a warehouse trying to get them to target locations.
The game is represented by a grid
of size n*
m
, where each element is a wall, floor, or a box.
Your task is move the box 'B'
to the target position 'T'
under the following rules:
- Player is represented by character
'S'
and can move up, down, left, right in thegrid
if it is a floor (empy cell). - Floor is represented by character
'.'
that means free cell to walk. - Wall is represented by character
'#'
that means obstacle (impossible to walk there). - There is only one box
'B'
and one target cell'T'
in thegrid
. - The box can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. This is a push.
- The player cannot walk through the box.
Return the minimum number of pushes to move the box to the target. If there is no way to reach the target, return -1
.
Example 1:
Input: grid = [["#","#","#","#","#","#"], ["#","T","#","#","#","#"], ["#",".",".","B",".","#"], ["#",".","#","#",".","#"], ["#",".",".",".","S","#"], ["#","#","#","#","#","#"]] Output: 3 Explanation: We return only the number of times the box is pushed.
Example 2:
Input: grid = [["#","#","#","#","#","#"], ["#","T","#","#","#","#"], ["#",".",".","B",".","#"], ["#","#","#","#",".","#"], ["#",".",".",".","S","#"], ["#","#","#","#","#","#"]] Output: -1
Example 3:
Input: grid = [["#","#","#","#","#","#"], ["#","T",".",".","#","#"], ["#",".","#","B",".","#"], ["#",".",".",".",".","#"], ["#",".",".",".","S","#"], ["#","#","#","#","#","#"]] Output: 5 Explanation: push the box down, left, left, up and up.
Example 4:
Input: grid = [["#","#","#","#","#","#","#"], ["#","S","#",".","B","T","#"], ["#","#","#","#","#","#","#"]] Output: -1
Constraints:
1 <= grid.length <= 20
1 <= grid[i].length <= 20
grid
contains only characters'.'
,'#'
,'S'
,'T'
, or'B'
.- There is only one character
'S'
,'B'
and'T'
in thegrid
.
Solution: BFS + DFS
BFS to search by push steps to find miminal number of pushes. Each time we move from the previous position (initial position or last push position) to a new push position. Use DFS to check that whether that path exist or not.
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 79 80 81 82 83 84 85 86 |
// Author: Huahua struct Node { int bx; int by; int px; int py; int key() const { return ((by * 20 + bx) << 16) | (py * 20 + px); } }; class Solution { public: int minPushBox(vector<vector<char>>& grid) { const int n = grid.size(); const int m = grid[0].size(); Node start; Node end; for (int y = 0; y < n; ++y) for (int x = 0; x < m; ++x) if (grid[y][x] == 'B') { start.bx = x; start.by = y; } else if (grid[y][x] == 'S') { start.px = x; start.py = y; } else if (grid[y][x] == 'T') { end.bx = x; end.by = y; } auto hasPath = [&](const Node& cur, int tx, int ty) { vector<int> seen(m*n); function<bool(int, int)> dfs = [&](int x, int y) { if (x < 0 || x >= m || y < 0 || y >= n || grid[y][x] == '#') return false; if (x == cur.bx && y == cur.by) return false; int key = y * m + x; if (seen[key]) return false; seen[key] = 1; if (x == tx && y == ty) return true; return dfs(x + 1, y) || dfs(x - 1, y) || dfs(x, y + 1) || dfs(x, y - 1); }; return dfs(cur.px, cur.py); }; auto canPush = [&](const Node& cur, int dx, int dy, Node* nxt) { const int bx = cur.bx + dx; const int by = cur.by + dy; if (bx < 0 || bx >= m || by < 0 || by >= n || grid[by][bx] == '#') return false; if (!hasPath(cur, cur.bx - dx, cur.by - dy)) return false; nxt->bx = bx; nxt->by = by; nxt->px = cur.bx; nxt->py = cur.by; return true; }; const vector<int> dirs{0, -1, 0, 1, 0}; unordered_set<int> seen; queue<Node> q; q.push(start); int steps = 0; while (q.size()) { int size = q.size(); while (size--) { Node cur = q.front(); q.pop(); for (int i = 0; i < 4; ++i) { Node nxt; if (!canPush(cur, dirs[i], dirs[i + 1], &nxt) || seen.count(nxt.key())) continue; if (nxt.bx == end.bx && nxt.by == end.by) return steps + 1; seen.insert(nxt.key()); q.push(nxt); } } ++steps; } return -1; } }; |
Solution: A* + BFS
g : history = # of pushes
h: heuristics = Manhattan distance from the current box position to the target position, always <= actual moves.
f = g + h
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 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
// Author: Huahua, 4 ms, 17.5 MB struct Node { int bx; int by; int px; int py; int h; int g; int key() const { return ((by * m + bx) << 2) | ((bx - px) + 1) | ((by - py) + 1) >> 1; } int f() const { return g + h; } bool operator< (const Node& o) const { return f() > o.f(); } static int m; }; int Node::m; class Solution { public: int minPushBox(vector<vector<char>>& grid) { const vector<int> dirs{0, -1, 0, 1, 0}; const int n = grid.size(); const int m = Node::m = grid[0].size(); Node start; Node end; for (int y = 0; y < n; ++y) for (int x = 0; x < m; ++x) if (grid[y][x] == 'B') { start.bx = x; start.by = y; } else if (grid[y][x] == 'S') { start.px = x; start.py = y; } else if (grid[y][x] == 'T') { end.bx = x; end.by = y; } auto isValid = [&](int x, int y) { return !(x < 0 || x >= m || y < 0 || y >= n || grid[y][x] == '#'); }; auto hasPath = [&](const Node& cur, int tx, int ty) { if (!isValid(tx, ty)) return false; vector<int> seen(m*n); queue<int> q; q.push(cur.py * m + cur.px); seen[cur.py * m + cur.px] = 1; while (q.size()) { int x = q.front() % m; int y = q.front() / m; q.pop(); for (int i = 0; i < 4; ++i) { int nx = x + dirs[i]; int ny = y + dirs[i + 1]; if (!isValid(nx, ny)) continue; if (nx == cur.bx && ny == cur.by) continue; if (nx == tx && ny == ty) return true; if (seen[ny * m + nx]++) continue; q.push(ny * m + nx); } } return false; }; auto canPush = [&](const Node& cur, int dx, int dy, Node* nxt) { nxt->bx = cur.bx + dx; nxt->by = cur.by + dy; nxt->px = cur.bx; nxt->py = cur.by; nxt->g = cur.g + 1; nxt->h = abs(nxt->bx - end.bx) + abs(nxt->by - end.by); if (!isValid(nxt->bx, nxt->by)) return false; return hasPath(cur, cur.bx - dx, cur.by - dy); }; vector<int> seen(m*n*4); priority_queue<Node> q; start.g = 0; start.h = abs(start.bx - end.bx) + abs(start.by - end.by); q.push(start); while (q.size()) { Node cur = q.top(); q.pop(); for (int i = 0; i < 4; ++i) { Node nxt; if (!canPush(cur, dirs[i], dirs[i + 1], &nxt) || seen[nxt.key()]++) continue; if (nxt.bx == end.bx && nxt.by == end.by) return nxt.g; q.push(nxt); } } return -1; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment