LeetCode 1263. 推箱子

Categories:

题目描述
思路分析
1. 解法一：BFS + 可达性判断（推荐）
相似题目

题目描述

✅ 1263. 推箱子

思路分析

解法一：BFS + 可达性判断（推荐）

核心思路：

状态由“箱子位置 + 人位置”构成，推箱子次数为 BFS 层级。

每次尝试向四个方向推箱子，需要先判断人能否到达箱子背面。

人的可达性通过 BFS（避开墙和箱子）判断。

复杂度分析：

时间复杂度：O((mn)^2)，其中 m、n 表示网格尺寸。

空间复杂度：O(mn)，用于 BFS 访问状态。

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int minPushBox(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] box = new int[2];
        int[] player = new int[2];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'B') {
                    box[0] = i;
                    box[1] = j;
                } else if (grid[i][j] == 'S') {
                    player[0] = i;
                    player[1] = j;
                }
            }
        }

        boolean[][][][] visited = new boolean[m][n][m][n];
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{box[0], box[1], player[0], player[1]});
        visited[box[0]][box[1]][player[0]][player[1]] = true;

        int pushes = 0;
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                int bx = cur[0];
                int by = cur[1];
                int px = cur[2];
                int py = cur[3];

                if (grid[bx][by] == 'T') {
                    return pushes;
                }

                for (int k = 0; k < 4; k++) {
                    int nbx = bx + dx[k];
                    int nby = by + dy[k];
                    int needX = bx - dx[k];
                    int needY = by - dy[k];

                    if (!inBound(nbx, nby, m, n) || grid[nbx][nby] == '#') {
                        continue;
                    }
                    if (!inBound(needX, needY, m, n) || grid[needX][needY] == '#') {
                        continue;
                    }

                    if (!canReach(grid, px, py, needX, needY, bx, by)) {
                        continue;
                    }

                    if (!visited[nbx][nby][bx][by]) {
                        visited[nbx][nby][bx][by] = true;
                        queue.offer(new int[]{nbx, nby, bx, by});
                    }
                }
            }
            pushes++;
        }

        return -1;
    }

    private boolean inBound(int x, int y, int m, int n) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    private boolean canReach(char[][] grid, int sx, int sy, int tx, int ty, int bx, int by) {
        int m = grid.length;
        int n = grid[0].length;

        boolean[][] vis = new boolean[m][n];
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{sx, sy});
        vis[sx][sy] = true;

        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            if (cur[0] == tx && cur[1] == ty) {
                return true;
            }
            for (int k = 0; k < 4; k++) {
                int nx = cur[0] + dx[k];
                int ny = cur[1] + dy[k];
                if (!inBound(nx, ny, m, n) || vis[nx][ny]) {
                    continue;
                }
                if (grid[nx][ny] == '#' || (nx == bx && ny == by)) {
                    continue;
                }
                vis[nx][ny] = true;
                q.offer(new int[]{nx, ny});
            }
        }

        return false;
    }
}

func minPushBox(grid [][]byte) int {
	m := len(grid)
	n := len(grid[0])
	var bx, by, px, py int

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 'B' {
				bx, by = i, j
			} else if grid[i][j] == 'S' {
				px, py = i, j
			}
		}
	}

	visited := make([][][][]bool, m)
	for i := 0; i < m; i++ {
		visited[i] = make([][][]bool, n)
		for j := 0; j < n; j++ {
			visited[i][j] = make([][]bool, m)
			for x := 0; x < m; x++ {
				visited[i][j][x] = make([]bool, n)
			}
		}
	}

	queue := make([][4]int, 0)
	queue = append(queue, [4]int{bx, by, px, py})
	visited[bx][by][px][py] = true

	pushes := 0
	dx := []int{1, -1, 0, 0}
	dy := []int{0, 0, 1, -1}

	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			cur := queue[i]
			bx, by = cur[0], cur[1]
			px, py = cur[2], cur[3]

			if grid[bx][by] == 'T' {
				return pushes
			}

			for k := 0; k < 4; k++ {
				nbx := bx + dx[k]
				nby := by + dy[k]
				needX := bx - dx[k]
				needY := by - dy[k]

				if !inBound(nbx, nby, m, n) || grid[nbx][nby] == '#' {
					continue
				}
				if !inBound(needX, needY, m, n) || grid[needX][needY] == '#' {
					continue
				}

				if !canReach(grid, px, py, needX, needY, bx, by) {
					continue
				}

				if !visited[nbx][nby][bx][by] {
					visited[nbx][nby][bx][by] = true
					queue = append(queue, [4]int{nbx, nby, bx, by})
				}
			}
		}
		queue = queue[size:]
		pushes++
	}

	return -1
}

func inBound(x int, y int, m int, n int) bool {
	return x >= 0 && x < m && y >= 0 && y < n
}

func canReach(grid [][]byte, sx int, sy int, tx int, ty int, bx int, by int) bool {
	m := len(grid)
	n := len(grid[0])

	vis := make([][]bool, m)
	for i := 0; i < m; i++ {
		vis[i] = make([]bool, n)
	}

	q := make([][2]int, 0)
	q = append(q, [2]int{sx, sy})
	vis[sx][sy] = true

	dx := []int{1, -1, 0, 0}
	dy := []int{0, 0, 1, -1}

	for len(q) > 0 {
		cur := q[0]
		q = q[1:]
		if cur[0] == tx && cur[1] == ty {
			return true
		}
		for k := 0; k < 4; k++ {
			nx := cur[0] + dx[k]
			ny := cur[1] + dy[k]
			if !inBound(nx, ny, m, n) || vis[nx][ny] {
				continue
			}
			if grid[nx][ny] == '#' || (nx == bx && ny == by) {
				continue
			}
			vis[nx][ny] = true
			q = append(q, [2]int{nx, ny})
		}
	}

	return false
}

相似题目

题目	难度	考察点
1263. 推箱子	困难	BFS、状态搜索
773. 滑动谜题	中等	BFS
1293. 网格中的最短路径	困难	BFS
934. 最短的桥	中等	BFS
490. 迷宫	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/13603620