CSU 1604 SunnyPig：豬穴逃脫 BFS - 單向門與邊界判定

題目描述

m×n 網格豬穴，牆壁用 | - 表示，門用 N/S/W/E 表示（只能從特定方向推開）。起點 O，求推開最少門數逃出邊界，不可則 -1。

關鍵建模

• 將原始 (2m+1)×(2n+1) 字符地圖轉換為 m×n 格子圖。每個格子中心對應原圖奇數行奇數列位置。
• 格子間移動對應原圖相鄰格子中心之間的字符：若為空格 ' ' 可直接通過；若為門 N/S/W/E，需檢查移動方向是否與門允許方向一致（如向北移動需門為 N），通過則門數 +1；牆壁 | - 不可通過。

BFS 狀態

(x, y, doors)：當前格子坐標、已推開門數。訪問標記 vis[x][y]，因 BFS 保證首次到達門數最少。

C++ 代碼實現（核心邏輯）

// 方向：0-無, 1-東, 2-南, 3-西, 4-北
int dirX[5] = {0, 1, 0, -1, 0};
int dirY[5] = {0, 0, 1, 0, -1};
char doorChar[5] = {0, 'E', 'S', 'W', 'N'};

bool canPass(int x, int y, int dir, int& cost) {
    char c = grid[x][y]; // 原圖對應邊界字符
    if (c == ' ') return true; // 空地
    if (c == doorChar[dir]) { cost = 1; return true; } // 正確方向的門
    return false; // 牆或反方向門
}

int bfs() {
    queue> q;
    q.emplace(sx, sy, 0);
    vis[sx][sy] = true;
    while (!q.empty()) {
        auto [x, y, d] = q.front(); q.pop();
        if (x==0 || x==m-1 || y==0 || y==n-1) return d; // 到達邊界
        for (int dir = 1; dir <= 4; ++dir) {
            int nx = x + dirX[dir], ny = y + dirY[dir];
            if (nx<0 || nx>=m || ny<0 || ny>=n || vis[nx][ny]) continue;
            int cost = 0;
            if (canPass(x, y, dir, cost)) {
                vis[nx][ny] = true;
                q.emplace(nx, ny, d + cost);
            }
        }
    }
    return -1;
}

關鍵點總結

1. 地圖轉換：原圖 (2i+1, 2j+1) 為格子 (i,j) 中心；邊界字符在 (2i+1+dx, 2j+1+dy)。
2. 門的方向性：N 門只能從南向北推（即移動方向為北），對應 dir=4。
3. BFS 層序保證最少門數，訪問標記防止重複入隊。