「Pushing Boxes」推箱子

形式化题目

给定 $N \times M$ 的网格，每格是墙（#）或空地（.）。空地中有三个特殊格子：人 $S$ 、箱子 $B$ 、目标 $T$ 。

一步操作只有两种：

走：人移动到相邻的空地，且该格不是箱子所在格；
推：箱子恰好在人前方一格，人朝箱子方向走一步，于是箱子前进一格；要求箱子前方那格是空地。

要求把箱子推到 $T$ 上（箱子到达 $T$ 的那一刻即结束，不要求人停在某处），并输出操作序列。记方案的推箱次数为 $P$ 、人走路步数为 $W$ ，则要求按以下顺序取最优：

$P$ 最小；
$P$ 相同时 $W$ 最小；
前两者都相同时，动作串字典序最小。字符优先级为

N < S < W < E < n < s < w < e

其中大写是推箱、小写是走路。无解时输出 Impossible.。

把"人在 $p$ 、箱子在 $b$ "记为一个状态，就得到一张有向图：

走边 $(p, b) \to (p', b)$ ： $p'$ 与 $p$ 四邻、 $p'$ 非墙且 $p' \neq b$ ，代价 $(\text{push}, \text{walk}) = (0, 1)$ ；
推边 $(p, b) \to (b, b + d)$ ：其中 $b = p + d$ 且 $b + d$ 非墙，代价 $(1, 0)$ 。

于是问题就是：求从起点到任意"箱子在 $T$ "状态的字典序最短路（先比 push 再比 walk），并输出其中字符优先级字典序最小的边序列。注意第 3 条只在代价完全相同的方案之间做选择，不会为了字典序而牺牲 $P$ 或 $W$ 。

正解

思路

朴素做法是状态图上的 Dijkstra。 状态只有 $(NM)^2$ 种，每种至多 5 条出边，用 heapq 以 $(\text{push}, \text{walk})$ 为键跑一遍最短路，就能求出最优的 $P$ 与 $W$ 。这一步没有任何困难，困难全在第三级优先级上。

瓶颈：堆比较不了动作串。 想把"动作串字典序"塞进堆，就得让堆元素携带整条动作串：

python

1heappush(pq, (push, walk, action_string, state))

$O(L)$ 的字符串比较和复制会混进每个堆操作（ $L$ 是答案串长度，真实数据中最长 588），既慢又难以论证。另一种常见写法"按优先级顺序扩展、每个状态只记第一次访问"则根本不对：第一次到达某状态的路径未必最优，把代价最优性和访问顺序耦合会直接丢掉正确答案。

关键性质 1：二维代价可以压成一个整数。 两种边权都是正的，所以最优方案必定是状态图上的简单路径：若路径含环，删掉环只会让 $P$ 和 $W$ 都不变大，得到的方案更优或一样优。状态数 $|V| = (NM)^2 \leqslant 160000 < 2^{20}$ ，所以最优方案的走路步数 $W < 2^{20}$ 。于是

c = P \cdot 2^{20} + W

把 $c$ 乘开就能看出： $P$ 不同则 $c$ 的大小完全由 $P$ 决定（低位最多影响 $2^{20}-1$ ）， $P$ 相同则退化成比 $W$ 。因此以 $c$ 为堆键跑出的最短路，就是 $P$ 最小、再 $W$ 最小的方案，堆里也只剩整数。

关键性质 2：贪心只需要"剩余代价"这一件信息。 记 $g(v)$ 为从状态 $v$ 出发走到终局的最小代价（按上面编码）。称边 $v \to u$ 是紧的，如果

g(v) = w(v,u) + g(u)

紧边恰好组成所有最优方案所在的子图。从起点出发，每一步只在紧边里挑优先级最高的动作，得到的动作串就是所有最优方案里字典序最小的：

设已走代价为 spent、当前状态满足 spent + g(v) = g(起点)。最优方案的下一个动作必然来自某条紧边（否则那条方案本身就非最优）。取所有紧边中优先级最高的动作 $a$ ，任取一个下一步走 $a' \neq a$ 的最优方案：因为 $a$ 是紧边，从它的目标状态出发存在代价恰为 $g(\text{next}_a)$ 的后缀，接在 $a$ 后就是一个总代价相同、而下一个字符优先级更小的合法方案，所以后者按第三级优先级更优；故必定存在下一步走 $a$ 的最优方案，贪心不劣。对每一步重复同样的论证，贪心选出的动作串就是同代价方案中字典序最小的那个。

关键性质 3： $g$ 要反向算。 正向 Dijkstra 得到的是"从起点到 $v$ 的最小代价"，而性质 2 需要的是"从 $v$ 到终局的最小代价"。区别只是把边反向：反向图的边权与正向完全相同，所以从所有"箱子已在 $T$ "的状态出发跑一次反向 Dijkstra，就一次性得到全部 $g(v)$ 。

g(v) = \min_{v \to u}\bigl(w(v,u) + g(u)\bigr), \qquad g\bigl((p, T)\bigr) = 0 \text{ 对任意空地 } p

反向边只有两种形态，都可以由正向规则直接读出来：

反向边	前驱状态	条件	权
反向走边	$(p', b)$	$p'$ 与 $p$ 四邻， $p'$ 非墙且 $p' \neq b$	$1$
反向推边	$(2p - b,\; p)$	$b$ 与 $p$ 相邻（箱子和人贴在一起）且 $2p - b$ 非墙	$2^{20}$

推边那一行要仔细：推完后人站在箱子的旧格子上，所以对当前状态 $(p, b)$ （此时 $b$ 是推完之后箱子所在的格子），推之前箱子在 $p$ 、人在 $2p - b$ 。

这两种边的关系可以用一张图说清：同一个局面出发，走路只改"人"这一半、代价走低位；推箱同时改两半、代价走高位的 $2^{20}$ 。

flowchart LR
    S0["状态<br/>(person, box)"] -->|"走一步<br/>w = (0,1)"| W1["(person', box)<br/>人变、箱子不变"]
    S0 -->|"推一步<br/>w = (1,0)"| P1["(box, box+d)<br/>人变、箱子前移"]
    W1 --> G["反向 Dijkstra<br/>g(v) = 到终局的最小代价"]
    P1 --> G
    G --> F["正向贪心<br/>只在紧边上走"]
    F --> Ans["动作串"]

图的左半部分解释了为什么每个状态恰好有两类边；右半部分说明 $g$ 只算数值、贪心只挑动作，两者分工明确，谁都不需要比较动作串。

完整的算法只有两步：

backward_cost：把所有 $(p, T)$ 以代价 0 入堆，按上表松弛反向边，得到 cost[v] = g(v)。一弹出起点状态就停止——此时起点的 $g$ 已定稿，路径上其余状态的 $g$ 都比它小，也早已定稿。
path_of：从起点出发，每次先看能不能走一条紧推边（spent + 2^20 + cost[next] == g(start)），能就走；否则按 $n, s, w, e$ 的顺序找第一条紧走边。只取紧边，所以走的一定是最优方案；按优先级取第一条，所以是其中字典序最小的那条。

用样例 #4（题面第 4 组数据，8 行 4 列）看答案串的构成。下表按"连续同类动作"切成 6 段，格子坐标写作 0 起的 (行, 列)：

段	动作	人移动到的格子	箱子所在格子	这一段在做什么
1	`s`	(6, 3)	(4, 3)	人从 `(5,3)` 下到 `(6,3)`，让开箱子所在的列
2	`www`	(6, 0)	(4, 3)	沿第 6 行向左走到第 0 列
3	`nnnnnn`	(0, 0)	(4, 3)	沿第 0 列一路向上爬到第 0 行
4	`eee`	(0, 3)	(4, 3)	沿第 0 行向右走到箱子所在列
5	`sss`	(3, 3)	(4, 3)	下到箱子北侧，贴住箱子
6	`SSS`	(6, 3)	(7, 3)	连续下推三次，把箱子从 `(4,3)` 推到 `T` 所在的 `(7,3)`

推箱 3 次、走路 16 步。前 5 段全是绕路，只有最后 3 步 SSS 真正推动了箱子；第 5 段结束时（人贴在箱子北侧）的局面是：

text

1
2
3
4
5
6
7
8....
.##.
.#..
.#.S
.#.B
.##.
....
###T

为什么必须绕这么远？箱子要从 (4,3) 被推到 T 所在的 (7,3)，只能由人从北侧往下推，所以人必须先站到 (3,3)。但人从 (5,3) 出发时，向上的 (4,3) 被箱子占着，向左的 (5,2) 和 (5,1) 都是墙，于是只能先下到第 6 行、沿它走到最左的 (6,0)，再沿第 0 列一路爬到 (0,0)，最后从第 0 行折回 (0,3) 再往下走到 (3,3)。推箱只需 3 次，人却走了 16 步——这就是 $P$ 与 $W$ 必须分开当两级优先级的原因：绕路是推箱的必然代价，但代价相同的方案之间仍然要挑绕得最少的那条。

无解不是一个特例分支：如果起点状态松弛不到，"箱子在 T"的状态就永远到不了， cost[start] 会保持哨兵值 INF，直接输出 Impossible. 即可。

代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 14:12
# update_at: 2026-10-01 14:17

import sys
from heapq import heapify, heappop, heappush

# 四个方向按题目优先级排列：箱子 N、S、W、E 与人 n、s、w、e 共用这张表，下标顺序就是优先级。
DIRS = ((-1, 0), (1, 0), (0, -1), (0, 1))
PUSH_CH = dict(zip(DIRS, "NSWE"))  # 人贴着箱子时，箱子朝该方向移动一格
WALK_CH = "nswe"                   # 人单独朝 DIRS[i] 方向移动一格
INF = 1 << 60
STEP = 1 << 20  # 推箱次数左移到高位：一次整数比较就完成「先比推箱数、再比走路步数」的字典序


def backward_cost(n: int, m: int, free: list[bool], target: int, start: int) -> list[int]:
    """每个状态到「箱子停在 T」的最小代价，编码为 推箱次数 * STEP + 走路步数。

    状态编号 = 人的格子 * nm + 箱子的格子。在状态图上以所有「箱子已在 T」的状态为源点
    反向 Dijkstra：反向的人移动 = 人原先站在当前格的四邻；反向的推箱 = 推完后人站在箱子
    旧格子上，所以人原先在箱子的另一侧。反向图每条边权和正向相同，算出的即正向最优值。
    一弹出起点状态就收工：此后不会再出现更小的值，路径上其余状态的代价都已定稿。
    """
    nm = n * m
    cost = [INF] * (nm * nm)
    heap = [(0, p * nm + target) for p in range(nm) if free[p]]  # 箱子已到 T，代价 0
    for value, state in heap:
        cost[state] = value
    heapify(heap)

    while heap:
        d, state = heappop(heap)
        if cost[state] != d:  # 堆里的过期条目
            continue
        if state == start:  # 起点的最优值定稿，更小的状态都已经出堆了
            break
        box, person = state % nm, state // nm
        br, bc = divmod(box, m)
        pr, pc = divmod(person, m)
        for dr, dc in DIRS:
            # 反向的人移动：人从四邻之一的格子走到 person，那格不能被箱子占着
            nr, nc = pr + dr, pc + dc
            near = nr * m + nc
            if 0 <= nr < n and 0 <= nc < m and free[near] and near != box:
                before = near * nm + box
                if d + 1 < cost[before]:  # 走路步数 +1，落在低位
                    cost[before] = d + 1
                    heappush(heap, (d + 1, before))
            # 反向的推箱：推完后人站在箱子的旧格子上，故人原先在箱子另一侧
            if abs(br - pr) + abs(bc - pc) == 1:  # 人和箱子贴在一起才谈得上推
                opr, opc = 2 * pr - br, 2 * pc - bc  # 推之前人的格子
                if 0 <= opr < n and 0 <= opc < m and free[opr * m + opc]:
                    before = (opr * m + opc) * nm + person  # 推之前箱子正站在 person 格
                    if d + STEP < cost[before]:  # 推箱次数 +1，落在高位
                        cost[before] = d + STEP
                        heappush(heap, (d + STEP, before))
    return cost


def path_of(n: int, m: int, free: list[bool], person: int, box: int, target: int,
            cost: list[int]) -> str:
    """贴着最优值贪心还原动作串：每步挑当前优先级最高且不破坏最优性的那个动作。"""
    nm = n * m
    limit = cost[person * nm + box]
    out: list[str] = []
    spent = 0
    while box != target:
        pr, pc = divmod(person, m)
        br, bc = divmod(box, m)
        dr, dc = br - pr, bc - pc  # 人指向箱子的方向，也就是推箱方向
        # ① 能推就推：推箱字母整体排在人移动字母之前，优先级更高
        if abs(dr) + abs(dc) == 1:
            nr, nc = br + dr, bc + dc
            if 0 <= nr < n and 0 <= nc < m and free[nr * m + nc]:
                after = box * nm + nr * m + nc  # 推完之后人站到箱子原来的格子
                if spent + STEP + cost[after] == limit:  # 走这条边仍落在最优解上
                    out.append(PUSH_CH[(dr, dc)])
                    person, box, spent = box, nr * m + nc, spent + STEP
                    continue
        # ② 否则人走一步，按 n、s、w、e 的顺序取第一个可行的方向
        for i, (dr, dc) in enumerate(DIRS):
            nr, nc = pr + dr, pc + dc
            step = nr * m + nc
            if 0 <= nr < n and 0 <= nc < m and free[step] and step != box:
                if spent + 1 + cost[step * nm + box] == limit:
                    out.append(WALK_CH[i])
                    person, spent = step, spent + 1
                    break
        else:  # 不做静默死循环：进入循环时保证 spent + cost[当前状态] == limit
            raise AssertionError(f"状态 {(person, box)} 上没有紧边")
    return "".join(out)


def solve() -> None:
    tokens = iter(sys.stdin.buffer.read().split())
    out: list[str] = []
    index = 0
    while True:
        n, m = int(next(tokens)), int(next(tokens))
        if n == 0 and m == 0:
            break
        index += 1
        grid = b"".join(next(tokens) for _ in range(n))
        nm = n * m
        free = [ch != 35 for ch in grid]  # 35 是 '#'：墙不可进入
        person, box, target = grid.index(83), grid.index(66), grid.index(84)
        start = person * nm + box
        cost = backward_cost(n, m, free, target, start)
        if cost[start] >= INF:  # 终点状态压根没被松弛到，方案不存在
            out.append(f"Maze #{index}\nImpossible.\n")
        else:
            moves = path_of(n, m, free, person, box, target, cost)
            out.append(f"Maze #{index}\n{moves}\n")
    print("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-04 22:31
 * update_at: 2026-10-04 22:31
 */
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <utility>
#include <cstdlib>
using namespace std;

typedef long long ll;

const int MAXN = 25;          // 网格最大行/列
const int MAXNM = 400;        // N * M <= 20 * 20
const int MAXV = MAXNM * MAXNM; // 状态数 (NM)^2
const ll INF = 1LL << 60;
const ll STEP = 1LL << 20;    // 一次推箱的代价，放在高位

// 四个方向按题目优先级 N < S < W < E（同时也是 n < s < w < e 的顺序）
const int DIRS[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
const char PUSH_CH[4] = {'N', 'S', 'W', 'E'};
const char WALK_CH[4] = {'n', 's', 'w', 'e'};

int n, m, nm;                 // 当前测试用例的行列与格子数
char grid[MAXN][MAXN];        // 原始地图
bool free_cell[MAXNM];        // free_cell[id] = 该格子不是墙
ll cost[MAXV];                // cost[state] = 从该状态到终局的最小编码代价

// 把二维坐标压成一维编号
inline int id(int r, int c) { return r * m + c; }

// 判断两个格子是否相邻
inline bool adjacent(int r1, int c1, int r2, int c2) {
    int dr = r1 - r2, dc = c1 - c2;
    return dr * dr + dc * dc == 1;
}

// 反向 Dijkstra：以所有「箱子已在 T」的状态为源点，求每个状态到终局的最小代价
void backward_cost(int person_start, int box_start, int target) {
    fill(cost, cost + nm * nm, INF);
    // 小根堆，(代价, 状态)
    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
    for (int p = 0; p < nm; ++p) {
        if (!free_cell[p]) continue;
        int state = p * nm + target;
        cost[state] = 0;
        pq.push(make_pair(0LL, state));
    }

    int start_state = person_start * nm + box_start;
    while (!pq.empty()) {
        pair<ll, int> cur = pq.top();
        pq.pop();
        ll d = cur.first;
        int state = cur.second;
        if (d != cost[state]) continue; // 过期条目
        if (state == start_state) break;  // 起点的最优值已定稿

        int person = state / nm;
        int box = state % nm;
        int pr = person / m, pc = person % m;
        int br = box / m, bc = box % m;

        // 反向的人移动：人从当前格子的某个四邻走到 person，箱子不动
        for (int i = 0; i < 4; ++i) {
            int nr = pr + DIRS[i][0];
            int nc = pc + DIRS[i][1];
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            int near = id(nr, nc);
            if (!free_cell[near] || near == box) continue;
            int before = near * nm + box;
            if (d + 1 < cost[before]) {
                cost[before] = d + 1;
                pq.push(make_pair(cost[before], before));
            }
        }

        // 反向的推箱：当前状态是推完之后，人站在箱子的旧格子上
        // 推之前箱子站在 person 格，人站在 person 关于 box 的对称格
        if (adjacent(pr, pc, br, bc)) {
            int opr = 2 * pr - br;
            int opc = 2 * pc - bc;
            if (0 <= opr && opr < n && 0 <= opc && opc < m) {
                int old_person = id(opr, opc);
                if (free_cell[old_person]) {
                    int before = old_person * nm + person;
                    if (d + STEP < cost[before]) {
                        cost[before] = d + STEP;
                        pq.push(make_pair(cost[before], before));
                    }
                }
            }
        }
    }
}

// 在紧边上按优先级贪心，还原字典序最小的最优动作串
string path_of(int person, int box, int target) {
    int start_state = person * nm + box;
    ll limit = cost[start_state];
    string ans;
    ll spent = 0;

    while (box != target) {
        int pr = person / m, pc = person % m;
        int br = box / m, bc = box % m;

        bool moved = false;

        // ① 若人贴着箱子，检查唯一可能的推箱动作是否为紧边
        if (adjacent(pr, pc, br, bc)) {
            int nr = 2 * br - pr; // 箱子被推后的新格子
            int nc = 2 * bc - pc;
            if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                int new_box = id(nr, nc);
                if (free_cell[new_box]) {
                    int after_state = box * nm + new_box;
                    if (spent + STEP + cost[after_state] == limit) {
                        // 推方向 = 箱子相对于人的位置（人指向箱子的向量）
                        int dr = br - pr;
                        int dc = bc - pc;
                        int dir_idx;
                        if (dr == -1) dir_idx = 0;          // N
                        else if (dr == 1) dir_idx = 1;       // S
                        else if (dc == -1) dir_idx = 2;     // W
                        else dir_idx = 3;                   // E
                        ans.push_back(PUSH_CH[dir_idx]);
                        person = box;
                        box = new_box;
                        spent += STEP;
                        moved = true;
                    }
                }
            }
        }

        if (moved) continue;

        // ② 否则按 n、s、w、e 的顺序找第一条紧的走路边
        for (int i = 0; i < 4; ++i) {
            int nr = pr + DIRS[i][0];
            int nc = pc + DIRS[i][1];
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            int next_person = id(nr, nc);
            if (!free_cell[next_person] || next_person == box) continue;
            int after_state = next_person * nm + box;
            if (spent + 1 + cost[after_state] == limit) {
                ans.push_back(WALK_CH[i]);
                person = next_person;
                spent += 1;
                moved = true;
                break;
            }
        }

        // 因为 limit 是最优代价，当前状态又满足 spent + cost[当前] == limit，
        // 所以必定存在一条紧边可以走。
        if (!moved) break;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string output;
    int case_idx = 0;
    while (cin >> n >> m) {
        if (n == 0 && m == 0) break;
        ++case_idx;
        nm = n * m;

        int person = -1, box = -1, target = -1;
        for (int i = 0; i < n; ++i) {
            cin >> grid[i];
            for (int j = 0; j < m; ++j) {
                int cell_id = id(i, j);
                char ch = grid[i][j];
                free_cell[cell_id] = (ch != '#');
                if (ch == 'S') person = cell_id;
                else if (ch == 'B') box = cell_id;
                else if (ch == 'T') target = cell_id;
            }
        }

        output += "Maze #";
        output += to_string(case_idx);
        output += "\n";

        backward_cost(person, box, target);
        int start_state = person * nm + box;
        if (cost[start_state] >= INF) {
            output += "Impossible.\n\n";
        } else {
            string moves = path_of(person, box, target);
            output += moves;
            output += "\n\n";
        }
    }

    cout << output;
    return 0;
}

复杂度

每组数据：状态数 $|V| = (NM)^2$ ，边数 $|E| \leqslant 5|V|$ 。

时间复杂度： $O\bigl((NM)^2 \log (NM)\bigr)$ 。 $N = M = 20$ 时 $|V| = 1.6 \times 10^5$ 、 $|E| < 8 \times 10^5$ ；真实数据 26 组、其中 8 个满盘，全部跑完约 0.33s。
空间复杂度： $O\bigl((NM)^2\bigr)$ ，cost 数组主导；满盘实测峰值 27MB，低于 128MB。

STEP 取 $2^{20}$ 而不是 $NM$ ：最长的简单路径有 $|V| - 1$ 条边，走路步数上界在 $10^5$ 量级，实测（真实数据 + 600 组随机 $20 \times 20$ 压力数据）最大值为 488， $2^{20}$ 留了充足余量。

总结

遇到"既要最优、又要在同代价方案里挑字典序最小"的搜索题，都可以拆成 反向最短路算剩余代价 + 正向只在紧边上贪心 两步。反向保证了 $g$ 是"从这里出发还要花多少"，贪心才有了裁判；正向保证了优先级顺序被逐位落实。
多级代价（推箱数、走路步数）压成一个整数 key 后，堆和紧边判定都退化成整数比较，这是本题在 Python 里能跑得动的前提。
状态图建模的要点是"两类边的定义与题面规则逐字对应"：走边要求目标格非墙且非箱子，推边要求箱子在人前方且前方非墙。反向推边的方向（推完人站在箱子旧格子）最容易写反，写反后样例里的长答案会直接变成 Impossible.。

图示解析

这张图串起本题从建模到输出动作串的主线：

text

1
2
3
4
5
6
7
8网格 + 行动规则
`- 状态 = (人的格子, 箱子的格子)，共 (NM)^2 个
   `- 边 = 人走一步 (推0,走1) / 推一步 (推1,走0)
      `- 反向 Dijkstra：所有「箱子在 T」的状态作源点
         |- 得到 g(v)：从 v 到终局的最少 (推箱数, 走路数)
         `- g(起点) 不可达 -> Impossible.
            `- 正向贪心：只在 spent + w + g(next) = g(起点) 的边里
               `- 按优先级 N < S < W < E < n < s < w < e 挑动作 -> 输出动作串

先看「状态」这一步：它把连续的手感问题变成了有限图上的最短路。再看反向 Dijkstra 的产物 g：它精确回答「从这里出发还要花多少代价」，因此正向每一步只要在保持最优性的边里挑优先级最高的动作，就得到字典序最小的方案。最后注意 Impossible. 不是一个特例分支，而是 g(起点) 仍为无穷大的自然结果。