# 1263. Minimum Moves to Move a Box to Their Target Location

A 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 an `m x n` grid of characters `grid` where each element is a wall, floor, or box.

Your task is to move the box `'B'` to the target position `'T'` under the following rules:

• The character `'S'` represents the player. The player can move up, down, left, right in `grid` if it is a floor (empty cell).
• The character `'.'` represents the floor which means a free cell to walk.
• The character `'#' `represents the wall which means an obstacle (impossible to walk there).
• There is only one box `'B'` and one target cell `'T'` in the `grid`.
• 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:

• `m == grid.length`
• `n == grid[i].length`
• `1 <= m, n <= 20`
• `grid` contains only characters `'.'``'#'``'S'``'T'`, or `'B'`.
• There is only one character `'S'``'B'`, and `'T'` in the `grid`.

``````class Solution {
public:
int minPushBox(vector<vector<char>>& grid) {
int res = 0, m = grid.size(), n = grid[0].size(), start = 0, target = 0, player = 0;
vector<vector<int>> dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
queue<pair<int, int>> q;
unordered_set<string> st;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 'B') start = i * n + j;
else if (grid[i][j] == 'T') target = i * n + j;
else if (grid[i][j] == 'S') player = i * n + j;
if (grid[i][j] != '#') grid[i][j] = '.';
}
}
q.push({start, player});
while (!q.empty()) {
for (int i = q.size(); i > 0; --i) {
auto t = q.front(); q.pop();
int box = t.first, player = t.second;
if (box == target) return res;
int xbox = box / n, ybox = box % n;
for (auto dir : dirs) {
int x = xbox + dir[0], y = ybox + dir[1], xp = xbox - dir[0], yp = ybox - dir[1];
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '#') continue;
if (xp < 0 || xp >= m || yp < 0 || yp >= n || grid[xp][yp] == '#') continue;
string str = to_string(box) + "_" + to_string(xp * n + yp);
if (st.count(str)) continue;
if (canReach(grid, player, xp * n + yp, box)) {
q.push({x * n + y, box});
st.insert(str);
}
}
}
++res;
}
return -1;
}
bool canReach(vector<vector<char>>& grid, int start, int target, int box) {
int m = grid.size(), n = grid[0].size();
queue<int> q{{start}};
vector<vector<int>> dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
vector<bool> visited(m * n);
visited[start] = true;
grid[box / n][box % n] = '#';
while (!q.empty()) {
int t = q.front(); q.pop();
if (t == target) {
grid[box / n][box % n] = '.';
return true;
}
int x0 = t / n, y0 = t % n;
for (auto &dir : dirs) {
int x = x0 + dir[0], y = y0 + dir[1];
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != '.' || visited[x * n + y]) continue;
visited[x * n + y] = true;
q.push(x * n + y);
}
}
grid[box / n][box % n] = '.';
return false;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1263

https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/

https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/discuss/431431/Java-straightforward-BFS-solution

https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/discuss/432593/cpp-two-bfs-solution-8ms-beat-100

LeetCode All in One 题目讲解汇总(持续更新中…)

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation