N×N 網格地圖，包含：空地、牆壁、起點 K、終點 T、鑰匙 (a-z)、門 (A-Z)、蛇 (S)。
規則：
• 拿到第 n 把鑰匙需先拿到 1..n-1（但可不拿鑰匙通過門格）。
• 蛇只能殺一次（殺後變空地）。
• 求從 K 到 T 的最短步數，不可達輸出 "impossible"。
狀態 = (x, y, keys, killed)
• keys：5 位掩碼，bit i 表示擁有第 i+1 把鑰匙（題目鑰匙 ≤ 5）。
• killed：0/1，是否已殺蛇。
• 訪問標記 vis[x][y][keys][killed] 存最小步數，BFS 保證最短路。
for 四個方向:
nx, ny = x+dx, y+dy
if 越界或牆壁: continue
nkeys = keys; nkilled = killed; nstep = step+1;
char c = map[nx][ny];
if (c >= 'a' && c <= 'z') { // 鑰匙
int id = c - 'a';
if (!(nkilled & (1<= 'A' && c <= 'Z') { // 門
int id = c - 'A';
if (nkeys == id) nkeys = id+1; // 擁有前 id 把鑰匙可開門（題目特殊規則）
} else if (c == 'S') { // 蛇
if (!(nkilled & (1< #include <bits/stdc++.h>
using namespace std;
struct Node { int x, y, keys, killed, step; };
int vis[110][110][32][2];
char mp[110][110];
int dx[4]={0,0,1,-1}, dy[4]={1,-1,0,0};
int bfs(int sx, int sy, int n, int m) {
memset(vis, 0x3f, sizeof(vis));
queue<Node> q;
q.push({sx, sy, 0, 0, 0});
vis[sx][sy][0][0] = 0;
while (!q.empty()) {
Node cur = q.front(); q.pop();
if (mp[cur.x][cur.y] == 'T' && cur.keys == m) return cur.step;
for (int d=0; d<4; d++) {
Node nxt = cur;
nxt.x += dx[d]; nxt.y += dy[d]; nxt.step++;
if (nxt.x<0||nxt.x>=n||nxt.y<0||nxt.y>=n) continue;
char c = mp[nxt.x][nxt.y];
if (c == '#') continue;
if (c >= 'a' && c <= 'z') {
int id = c - 'a';
if (!(nxt.killed & (1<= 'A' && c <= 'Z') {
int id = c - 'A';
if (nxt.keys == id) nxt.keys = id+1;
} else if (c == 'S') {
if (!(nxt.killed & 1)) { nxt.killed |= 1; nxt.step++; }
}
if (nxt.step < vis[nxt.x][nxt.y][nxt.keys][nxt.killed]) {
vis[nxt.x][nxt.y][nxt.keys][nxt.killed] = nxt.step;
q.push(nxt);
}
}
}
return -1;
}
int main() {
int n, m;
while (scanf("%d%d", &n, &m) == 2 && (n||m)) {
for (int i=0; i keys == id 判斷）。HDU 5025 是「多層約束最短路」的典型狀態壓縮 BFS：鑰匙順序、一次性殺蛇、門開啟條件，均編碼進狀態掩碼。關鍵在於正確理解題目特殊規則（門開啟條件、蛇與鑰匙共用位），並用 vis[x][y][mask][killed] 剪枝。模板通用性強，可擴展到更多鑰匙/道具類迷宮問題。
