题解：P13937 [蓝桥杯 2022 省 Java B] 拉箱子

lcyxds · 2025-10-23 19:07:23 · 题解

Java 组题当然要用 Java 做。

发现只有 O\!\left(n^3m^3\right) 种状态（枚举小人、箱子、终点的位置，各 O\!\left(nm\right) 种，且小人不与箱子重叠），其中如果三者皆不重叠则计入答案。不妨从终点开始反向搜索有多少合法位置，拉箱子的逆过程为推箱子。对于每一个状态，至多有五个后继状态：向四个方向移动以及推箱子。于是我们从每一个箱子和终点重叠的合法状态开始进行记忆化搜索，同时记录答案。时间复杂度 O\!\left(n^3m^3\right)。

import java.util.Scanner;

public class Main {
    Scanner cin = new Scanner(System.in);
    int[][] grid;
    int n;
    int m;

    boolean[][][][][][] state;

    int[][] DELTAS = { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };

    int res = 0;

    void Dfs(int px, int py, int cx, int cy, int dx, int dy) {
        if (!state[px][py][cx][cy][dx][dy]) {
            state[px][py][cx][cy][dx][dy] = true;
            if ((cx != dx || cy != dy) && (px != dx || py != dy)) {
                res++;
            }
            for (int[] delta : DELTAS) {
                int x = px + delta[0];
                int y = py + delta[1];
                if (x > -1 && x < n && y > -1 && y < m && grid[x][y] == 0 && (x != cx || y != cy)) {
                    Dfs(x, y, cx, cy, dx, dy);
                }
            }
            if (Math.abs(px - cx) + Math.abs(py - cy) == 1) {
                int x = cx * 2 - px;
                int y = cy * 2 - py;
                if (x > -1 && x < n && y > -1 && y < m && grid[x][y] == 0) {
                    Dfs(cx, cy, x, y, dx, dy);
                }
            }
        }
    }

    void Solve() {
        n = cin.nextInt();
        m = cin.nextInt();
        grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = cin.nextInt();
            }
        }
        state = new boolean[n][m][n][m][n][m];
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < m; b++) {
                if (grid[a][b] == 0) {
                    for (int c = 0; c < n; c++) {
                        for (int d = 0; d < m; d++) {
                            if ((c != a || d != b) && grid[c][d] == 0) {
                                Dfs(a, b, c, d, c, d);
                            }
                        }
                    }
                }
            }
        }
        System.out.print(res);
    }

    public static void main(String[] args) {
        new Main().Solve();
    }
}