上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution {
public:
int minPushBox(vector<vector<char>>& grid) {
}
};
java 解法, 执行用时: 14 ms, 内存消耗: 42.4 MB, 提交时间: 2023-05-08 09:45:17
class Solution {
public int minPushBox(char[][] grid) {
int m = grid.length, n = grid[0].length;
int sx = -1, sy = -1, bx = -1, by = -1; // 玩家、箱子的初始位置
for (int x = 0; x < m; x++) {
for (int y = 0; y < n; y++) {
if (grid[x][y] == 'S') {
sx = x;
sy = y;
} else if (grid[x][y] == 'B') {
bx = x;
by = y;
}
}
}
int[] d = {0, -1, 0, 1, 0};
int[][] dp = new int[m * n][m * n];
for (int i = 0; i < m * n; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
Queue<int[]> queue = new ArrayDeque<int[]>();
dp[sx * n + sy][bx * n + by] = 0; // 初始状态的推动次数为 0
queue.offer(new int[]{sx * n + sy, bx * n + by});
while (!queue.isEmpty()) {
Queue<int[]> queue1 = new ArrayDeque<int[]>();
while (!queue.isEmpty()) {
int[] arr = queue.poll();
int s1 = arr[0], b1 = arr[1];
int sx1 = s1 / n, sy1 = s1 % n, bx1 = b1 / n, by1 = b1 % n;
if (grid[bx1][by1] == 'T') { // 箱子已被推到目标处
return dp[s1][b1];
}
for (int i = 0; i < 4; i++) { // 玩家向四个方向移动到另一个状态
int sx2 = sx1 + d[i], sy2 = sy1 + d[i + 1], s2 = sx2*n+sy2;
if (!ok(grid, m, n, sx2, sy2)) { // 玩家位置不合法
continue;
}
if (bx1 == sx2 && by1 == sy2) { // 推动箱子
int bx2 = bx1 + d[i], by2 = by1 + d[i + 1], b2 = bx2*n+by2;
if (!ok(grid, m, n, bx2, by2) || dp[s2][b2] <= dp[s1][b1] + 1) { // 箱子位置不合法 或 状态已访问
continue;
}
dp[s2][b2] = dp[s1][b1] + 1;
queue1.offer(new int[]{s2, b2});
} else {
if (dp[s2][b1] <= dp[s1][b1]) { // 状态已访问
continue;
}
dp[s2][b1] = dp[s1][b1];
queue.offer(new int[]{s2, b1});
}
}
}
queue = queue1;
}
return -1;
}
public boolean ok(char[][] grid, int m, int n, int x, int y) { // 不越界且不在墙上
return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != '#';
}
}
golang 解法, 执行用时: 12 ms, 内存消耗: 6.6 MB, 提交时间: 2023-05-08 09:45:00
func minPushBox(grid [][]byte) int {
m, n := len(grid), len(grid[0])
var sx, sy, bx, by int // 玩家、箱子的初始位置
for x := 0; x < m; x++ {
for y := 0; y < n; y++ {
if grid[x][y] == 'S' {
sx, sy = x, y
} else if grid[x][y] == 'B' {
bx, by = x, y
}
}
}
ok := func(x, y int) bool { // 不越界且不在墙上
return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != '#'
}
d := []int{0, -1, 0, 1, 0}
dp := make([][]int, m * n)
for i := 0; i < m * n; i++ {
dp[i] = make([]int, m * n)
for j := 0; j < m * n; j++ {
dp[i][j] = 0x3f3f3f3f
}
}
dp[sx*n+sy][bx*n+by] = 0 // 初始状态的推动次数为 0
q := [][2]int{{sx*n+sy, bx*n+by}}
for len(q) > 0 {
q1 := [][2]int{}
for len(q) > 0 {
s1, b1 := q[0][0], q[0][1]
q = q[1:]
sx1, sy1, bx1, by1 := s1 / n, s1 % n, b1 / n, b1 % n
if grid[bx1][by1] == 'T' { // 箱子已被推到目标处
return dp[s1][b1]
}
for i := 0; i < 4; i++ { // 玩家向四个方向移动到另一个状态
sx2, sy2 := sx1 + d[i], sy1 + d[i + 1]
s2 := sx2*n+sy2
if !ok(sx2, sy2) { // 玩家位置不合法
continue
}
if bx1 == sx2 && by1 == sy2 { // 推动箱子
bx2, by2 := bx1 + d[i], by1 + d[i + 1]
b2 := bx2*n+by2
if !ok(bx2, by2) || dp[s2][b2] <= dp[s1][b1] + 1 { // 箱子位置不合法 或 状态已访问
continue
}
dp[s2][b2] = dp[s1][b1] + 1
q1 = append(q1, [2]int{s2, b2})
} else {
if dp[s2][b1] <= dp[s1][b1] { // 状态已访问
continue
}
dp[s2][b1] = dp[s1][b1]
q = append(q, [2]int{s2, b1})
}
}
}
q = q1
}
return -1
}
python3 解法, 执行用时: 292 ms, 内存消耗: 17.5 MB, 提交时间: 2023-05-08 09:44:33
class Solution:
def minPushBox(self, grid: List[List[str]]) -> int:
m = len(grid)
n = len(grid[0])
sx, sy, bx, by = None, None, None, None # 玩家、箱子的初始位置
for x in range(m):
for y in range(n):
if grid[x][y] == 'S':
sx = x
sy = y
elif grid[x][y] == 'B':
bx = x
by = y
# 不越界且不在墙上
def ok(x, y):
return (0 <= x < m and 0 <= y < n and grid[x][y] != '#')
d = [0, -1, 0, 1, 0]
dp = [[float('inf')] * (m * n) for _ in range(m * n)]
dp[sx * n + sy][bx * n + by] = 0 # 初始状态的推动次数为 0
q = deque([(sx * n + sy, bx * n + by)])
while q:
q1 = deque()
while q:
s1, b1 = q.popleft()
sx1, sy1 = s1 // n, s1 % n
bx1, by1 = b1 // n, b1 % n
if grid[bx1][by1] == 'T': # 箱子已被推到目标处
return dp[s1][b1]
for i in range(4): # 玩家向四个方向移动到另一个状态
sx2, sy2 = sx1 + d[i], sy1 + d[i + 1]
s2 = sx2 * n + sy2
if not ok(sx2, sy2): # 玩家位置不合法
continue
if sx2 == bx1 and sy2 == by1: # 推动箱子
bx2, by2 = bx1 + d[i], by1 + d[i + 1]
b2 = bx2 * n + by2
if not ok(bx2, by2) or dp[s2][b2] <= dp[s1][b1] + 1: # 箱子位置不合法 或 状态已访问
continue
dp[s2][b2] = dp[s1][b1] + 1
q1.append((s2, b2))
else:
if dp[s2][b1] <= dp[s1][b1]: # 状态已访问
continue
dp[s2][b1] = dp[s1][b1]
q.append((s2, b1))
q, q1 = q1, q
return -1
