Description#
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.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 20grid contains only characters '.', '#', 'S', 'T', or 'B'.- There is only one character
'S', 'B', and 'T' in the grid.
Solutions#
Solution 1: Double-ended Queue + BFS#
We consider the player’s position and the box’s position as a state, i.e., $(s_i, s_j, b_i, b_j)$, where $(s_i, s_j)$ is the player’s position, and $(b_i, b_j)$ is the box’s position. In the code implementation, we define a function $f(i, j)$, which maps the two-dimensional coordinates $(i, j)$ to a one-dimensional state number, i.e., $f(i, j) = i \times n + j$, where $n$ is the number of columns in the grid. So the player and the box’s state is $(f(s_i, s_j), f(b_i, b_j))$.
First, we traverse the grid to find the initial positions of the player and the box, denoted as $(s_i, s_j)$ and $(b_i, b_j)$.
Then, we define a double-ended queue $q$, where each element is a triplet $(f(s_i, s_j), f(b_i, b_j), d)$, indicating that the player is at $(s_i, s_j)$, the box is at $(b_i, b_j)$, and $d$ pushes have been made. Initially, we add $(f(s_i, s_j), f(b_i, b_j), 0)$ to the queue $q$.
Additionally, we use a two-dimensional array $vis$ to record whether each state has been visited. Initially, $vis[f(s_i, s_j), f(b_i, b_j)]$ is marked as visited.
Next, we start the breadth-first search.
In each step of the search, we take out the queue head element $(f(s_i, s_j), f(b_i, b_j), d)$, and check whether $grid[b_i][b_j] = ‘T’$ is satisfied. If it is, it means the box has been pushed to the target position, and now $d$ can be returned as the answer.
Otherwise, we enumerate the player’s next move direction. The player’s new position is denoted as $(s_x, s_y)$. If $(s_x, s_y)$ is a valid position, we judge whether $(s_x, s_y)$ is the same as the box’s position $(b_i, b_j)$:
- If they are the same, it means the player has reached the box’s position and pushed the box forward by one step. The box’s new position is $(b_x, b_y)$. If $(b_x, b_y)$ is a valid position, and the state $(f(s_x, s_y), f(b_x, b_y))$ has not been visited, then we add $(f(s_x, s_y), f(b_x, b_y), d + 1)$ to the end of the queue $q$, and mark $vis[f(s_x, s_y), f(b_x, b_y)]$ as visited.
- If they are different, it means the player has not pushed the box. Then we only need to judge whether the state $(f(s_x, s_y), f(b_i, b_j))$ has been visited. If it has not been visited, then we add $(f(s_x, s_y), f(b_i, b_j), d)$ to the head of the queue $q$, and mark $vis[f(s_x, s_y), f(b_i, b_j)]$ as visited.
We continue the breadth-first search until the queue is empty.
Note, if the box is pushed, the push count $d$ needs to be incremented by $1$, and the new state is added to the end of the queue $q$. If the box is not pushed, the push count $d$ remains unchanged, and the new state is added to the head of the queue $q$.
Finally, if no valid push scheme is found, then return $-1$.
The time complexity is $O(m^2 \times n^2)$, and the space complexity is $O(m^2 \times n^2)$. Where $m$ and $n$ are the number of rows and columns in the grid, respectively.
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
| class Solution:
def minPushBox(self, grid: List[List[str]]) -> int:
def f(i: int, j: int) -> int:
return i * n + j
def check(i: int, j: int) -> bool:
return 0 <= i < m and 0 <= j < n and grid[i][j] != "#"
for i, row in enumerate(grid):
for j, c in enumerate(row):
if c == "S":
si, sj = i, j
elif c == "B":
bi, bj = i, j
m, n = len(grid), len(grid[0])
dirs = (-1, 0, 1, 0, -1)
q = deque([(f(si, sj), f(bi, bj), 0)])
vis = [[False] * (m * n) for _ in range(m * n)]
vis[f(si, sj)][f(bi, bj)] = True
while q:
s, b, d = q.popleft()
bi, bj = b // n, b % n
if grid[bi][bj] == "T":
return d
si, sj = s // n, s % n
for a, b in pairwise(dirs):
sx, sy = si + a, sj + b
if not check(sx, sy):
continue
if sx == bi and sy == bj:
bx, by = bi + a, bj + b
if not check(bx, by) or vis[f(sx, sy)][f(bx, by)]:
continue
vis[f(sx, sy)][f(bx, by)] = True
q.append((f(sx, sy), f(bx, by), d + 1))
elif not vis[f(sx, sy)][f(bi, bj)]:
vis[f(sx, sy)][f(bi, bj)] = True
q.appendleft((f(sx, sy), f(bi, bj), d))
return -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
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
| class Solution {
private int m;
private int n;
private char[][] grid;
public int minPushBox(char[][] grid) {
m = grid.length;
n = grid[0].length;
this.grid = grid;
int si = 0, sj = 0, bi = 0, bj = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 'S') {
si = i;
sj = j;
} else if (grid[i][j] == 'B') {
bi = i;
bj = j;
}
}
}
int[] dirs = {-1, 0, 1, 0, -1};
Deque<int[]> q = new ArrayDeque<>();
boolean[][] vis = new boolean[m * n][m * n];
q.offer(new int[] {f(si, sj), f(bi, bj), 0});
vis[f(si, sj)][f(bi, bj)] = true;
while (!q.isEmpty()) {
var p = q.poll();
int d = p[2];
bi = p[1] / n;
bj = p[1] % n;
if (grid[bi][bj] == 'T') {
return d;
}
si = p[0] / n;
sj = p[0] % n;
for (int k = 0; k < 4; ++k) {
int sx = si + dirs[k], sy = sj + dirs[k + 1];
if (!check(sx, sy)) {
continue;
}
if (sx == bi && sy == bj) {
int bx = bi + dirs[k], by = bj + dirs[k + 1];
if (!check(bx, by) || vis[f(sx, sy)][f(bx, by)]) {
continue;
}
vis[f(sx, sy)][f(bx, by)] = true;
q.offer(new int[] {f(sx, sy), f(bx, by), d + 1});
} else if (!vis[f(sx, sy)][f(bi, bj)]) {
vis[f(sx, sy)][f(bi, bj)] = true;
q.offerFirst(new int[] {f(sx, sy), f(bi, bj), d});
}
}
}
return -1;
}
private int f(int i, int j) {
return i * n + j;
}
private boolean check(int i, int j) {
return i >= 0 && i < m && j >= 0 && j < n && grid[i][j] != '#';
}
}
|
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
| class Solution {
public:
int minPushBox(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
int si, sj, bi, bj;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 'S') {
si = i, sj = j;
} else if (grid[i][j] == 'B') {
bi = i, bj = j;
}
}
}
auto f = [&](int i, int j) {
return i * n + j;
};
auto check = [&](int i, int j) {
return i >= 0 && i < m && j >= 0 && j < n && grid[i][j] != '#';
};
int dirs[5] = {-1, 0, 1, 0, -1};
deque<tuple<int, int, int>> q;
q.emplace_back(f(si, sj), f(bi, bj), 0);
bool vis[m * n][m * n];
memset(vis, false, sizeof(vis));
vis[f(si, sj)][f(bi, bj)] = true;
while (!q.empty()) {
auto [s, b, d] = q.front();
q.pop_front();
si = s / n, sj = s % n;
bi = b / n, bj = b % n;
if (grid[bi][bj] == 'T') {
return d;
}
for (int k = 0; k < 4; ++k) {
int sx = si + dirs[k], sy = sj + dirs[k + 1];
if (!check(sx, sy)) {
continue;
}
if (sx == bi && sy == bj) {
int bx = bi + dirs[k], by = bj + dirs[k + 1];
if (!check(bx, by) || vis[f(sx, sy)][f(bx, by)]) {
continue;
}
vis[f(sx, sy)][f(bx, by)] = true;
q.emplace_back(f(sx, sy), f(bx, by), d + 1);
} else if (!vis[f(sx, sy)][f(bi, bj)]) {
vis[f(sx, sy)][f(bi, bj)] = true;
q.emplace_front(f(sx, sy), f(bi, bj), d);
}
}
}
return -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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| func minPushBox(grid [][]byte) int {
m, n := len(grid), len(grid[0])
var si, sj, bi, bj int
for i, row := range grid {
for j, c := range row {
if c == 'S' {
si, sj = i, j
} else if c == 'B' {
bi, bj = i, j
}
}
}
f := func(i, j int) int {
return i*n + j
}
check := func(i, j int) bool {
return i >= 0 && i < m && j >= 0 && j < n && grid[i][j] != '#'
}
q := [][]int{[]int{f(si, sj), f(bi, bj), 0}}
vis := make([][]bool, m*n)
for i := range vis {
vis[i] = make([]bool, m*n)
}
vis[f(si, sj)][f(bi, bj)] = true
dirs := [5]int{-1, 0, 1, 0, -1}
for len(q) > 0 {
p := q[0]
q = q[1:]
si, sj, bi, bj = p[0]/n, p[0]%n, p[1]/n, p[1]%n
d := p[2]
if grid[bi][bj] == 'T' {
return d
}
for k := 0; k < 4; k++ {
sx, sy := si+dirs[k], sj+dirs[k+1]
if !check(sx, sy) {
continue
}
if sx == bi && sy == bj {
bx, by := bi+dirs[k], bj+dirs[k+1]
if !check(bx, by) || vis[f(sx, sy)][f(bx, by)] {
continue
}
vis[f(sx, sy)][f(bx, by)] = true
q = append(q, []int{f(sx, sy), f(bx, by), d + 1})
} else if !vis[f(sx, sy)][f(bi, bj)] {
vis[f(sx, sy)][f(bi, bj)] = true
q = append([][]int{[]int{f(sx, sy), f(bi, bj), d}}, q...)
}
}
}
return -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
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
| function minPushBox(grid: string[][]): number {
const [m, n] = [grid.length, grid[0].length];
let [si, sj, bi, bj] = [0, 0, 0, 0];
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === 'S') {
[si, sj] = [i, j];
} else if (grid[i][j] === 'B') {
[bi, bj] = [i, j];
}
}
}
const f = (i: number, j: number): number => i * n + j;
const check = (i: number, j: number): boolean =>
i >= 0 && i < m && j >= 0 && j < n && grid[i][j] !== '#';
const q: Deque<[number, number, number]> = new Deque();
const vis: boolean[][] = new Array(m * n).fill(0).map(() => new Array(m * n).fill(false));
q.push([f(si, sj), f(bi, bj), 0]);
vis[f(si, sj)][f(bi, bj)] = true;
const dirs: number[] = [-1, 0, 1, 0, -1];
while (q.size() > 0) {
const [s, b, d] = q.shift()!;
const [si, sj] = [Math.floor(s / n), s % n];
const [bi, bj] = [Math.floor(b / n), b % n];
if (grid[bi][bj] === 'T') {
return d;
}
for (let k = 0; k < 4; ++k) {
const [sx, sy] = [si + dirs[k], sj + dirs[k + 1]];
if (!check(sx, sy)) {
continue;
}
if (sx === bi && sy === bj) {
const [bx, by] = [bi + dirs[k], bj + dirs[k + 1]];
if (!check(bx, by) || vis[f(sx, sy)][f(bx, by)]) {
continue;
}
vis[f(sx, sy)][f(bx, by)] = true;
q.push([f(sx, sy), f(bx, by), d + 1]);
} else if (!vis[f(sx, sy)][f(bi, bj)]) {
vis[f(sx, sy)][f(bi, bj)] = true;
q.unshift([f(sx, sy), f(bi, bj), d]);
}
}
}
return -1;
}
/* 以下是双向列队模板类 */
class CircularDeque<T> {
prev: CircularDeque<T> | null;
next: CircularDeque<T> | null;
begin: number;
end: number;
empty: boolean;
data: T[];
constructor(N: number) {
this.prev = this.next = null;
this.begin = this.end = 0;
this.empty = true;
this.data = Array(N);
}
isFull(): boolean {
return this.end === this.begin && !this.empty;
}
isEmpty(): boolean {
return this.empty;
}
push(val: T): boolean {
if (this.isFull()) return false;
this.empty = false;
this.data[this.end] = val;
this.end = (this.end + 1) % this.data.length;
return true;
}
front(): T | undefined {
return this.isEmpty() ? undefined : this.data[this.begin];
}
back(): T | undefined {
return this.isEmpty() ? undefined : this.data[this.end - 1];
}
pop(): T | undefined {
if (this.isEmpty()) return undefined;
const value = this.data[this.end - 1];
this.end = (this.end - 1) % this.data.length;
if (this.end < 0) this.end += this.data.length;
if (this.end === this.begin) this.empty = true;
return value;
}
unshift(val: T): boolean {
if (this.isFull()) return false;
this.empty = false;
this.begin = (this.begin - 1) % this.data.length;
if (this.begin < 0) this.begin += this.data.length;
this.data[this.begin] = val;
return true;
}
shift(): T | undefined {
if (this.isEmpty()) return undefined;
const value = this.data[this.begin];
this.begin = (this.begin + 1) % this.data.length;
if (this.end === this.begin) this.empty = true;
return value;
}
*values(): Generator<T, void, undefined> {
if (this.isEmpty()) return undefined;
let i = this.begin;
do {
yield this.data[i];
i = (i + 1) % this.data.length;
} while (i !== this.end);
}
}
class Deque<T> {
head: CircularDeque<T>;
tail: CircularDeque<T>;
_size: number;
constructor(collection: T[] = []) {
this.head = new CircularDeque<T>(128);
this.tail = new CircularDeque<T>(128);
this.tail.empty = this.head.empty = false;
this.tail.prev = this.head;
this.head.next = this.tail;
this._size = 0;
for (const item of collection) this.push(item);
}
size(): number {
return this._size;
}
push(val: T): void {
let last = this.tail.prev!;
if (last.isFull()) {
const inserted = new CircularDeque<T>(128);
this.tail.prev = inserted;
inserted.next = this.tail;
last.next = inserted;
inserted.prev = last;
last = inserted;
}
last.push(val);
this._size++;
}
back(): T | undefined {
if (this._size === 0) return;
return this.tail.prev!.back();
}
pop(): T | undefined {
if (this.head.next === this.tail) return undefined;
const last = this.tail.prev!;
const value = last.pop();
if (last.isEmpty()) {
this.tail.prev = last.prev;
last.prev!.next = this.tail;
}
this._size--;
return value;
}
unshift(val: T): void {
let first = this.head.next!;
if (first.isFull()) {
const inserted = new CircularDeque<T>(128);
this.head.next = inserted;
inserted.prev = this.head;
inserted.next = first;
first.prev = inserted;
first = inserted;
}
first.unshift(val);
this._size++;
}
shift(): T | undefined {
if (this.head.next === this.tail) return undefined;
const first = this.head.next!;
const value = first.shift();
if (first.isEmpty()) {
this.head.next = first.next;
first.next!.prev = this.head;
}
this._size--;
return value;
}
front(): T | undefined {
if (this._size === 0) return undefined;
return this.head.next!.front();
}
*values(): Generator<T, void, undefined> {
let node = this.head.next!;
while (node !== this.tail) {
for (const value of node.values()) yield value;
node = node.next!;
}
}
}
|
