HDU 2102 A 計劃：雙層迷宮 DFS 搜索與傳送門機制詳解

題目大意

兩張 N×M 迷宮地圖（N,M ≤ 12），每格可能為牆(#)、路(.)、傳送門(*)、起點(S)、終點(P)。玩家從某層 S 出發，每步可上下左右移動至非牆格。踩到傳送門(*)必須瞬間傳送到另一層同坐標，且該目標格不能為牆或傳送門。限制總步數 ≤ lim。判斷是否能在步數限制內到達終點 P（需同層）。

DFS 狀態定義

dfs(x, y, layer, steps)：當前位置 (x,y)、所在層 layer∈{0,1}、已用步數 steps。
訪問標記 vis[layer][x][y] 防止同層重複搜索（傳送門強制換層，不需標記目標層）。

關鍵邏輯

1. 移動合法性：
   - 目標格在邊界內
   - 當前層目標格不為牆
   - 若目標格為傳送門(*)：另一層同坐標必須為路(.)（不能為牆、傳送門、已訪問）
2. 傳送門處理：
   - 遇 *：檢查另一層同坐標合法 → 標記另一層訪問 → 遞歸 dfs(nx, ny, 1-layer, steps+1) → 回溯取消標記
3. 普通移動：
   - 目標格為路/起點/終點 → 標記當前層訪問 → 遞歸同層 → 回溯
4. 終止條件：
   - 到達終點且層正確且 steps ≤ lim → 返回 true
   - steps > lim → 返回 false

完整代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 12;
char mp[2][MAXN][MAXN];
bool vis[2][MAXN][MAXN];
int dx[4] = {0,0,-1,1}, dy[4] = {-1,1,0,0};
int N, M, lim, sx, sy, sl, tx, ty, tl;

bool ok(int x, int y) { return x>=0 && x=0 && y lim) return false;
    for (int d=0; d<4; ++d) {
        int nx=x+dx[d], ny=y+dy[d];
        if (!ok(nx,ny)) continue;
        if (mp[layer][nx][ny] == '*') { // 傳送門
            int nl = 1-layer;
            if (mp[nl][nx][ny] != '.' && mp[nl][nx][ny] != 'P' && mp[nl][nx][ny] != 'S') continue;
            if (vis[nl][nx][ny]) continue;
            vis[nl][nx][ny] = true;
            if (dfs(nx, ny, nl, step+1)) return true;
            vis[nl][nx][ny] = false;
        } else if (mp[layer][nx][ny] != '#' && !vis[layer][nx][ny]) { // 普通路
            vis[layer][nx][ny] = true;
            if (dfs(nx, ny, layer, step+1)) return true;
            vis[layer][nx][ny] = false;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        cin >> N >> M >> lim;
        for (int l=0; l<2; ++l)
            for (int i=0; i> mp[l][i];
                for (int j=0; j