NYOJ 375 突破包圍：雙層 BFS 窮舉所有可能路徑

問題場景

網格地圖中 'y' 為起點，'d' 為終點，'*' 為可拾取道具，'x' 為障礙。每步最多走 record[k] 步（k 為已拾取道具數）。求是否能到達終點。

雙層 BFS 策略

• 外層隊列 存儲「拾取道具後的狀態」：{x, y, k}，k 為已拾取道具數。
• 內層 BFS：從當前狀態出發，在步數限制 record[k] 內探索，遇到 '*' 且 k < K 時，生成新狀態 {nx, ny, k+1} 推入外層隊列。
• 訪問標記 visited 針對內層 BFS 重置；pro 標記道具是否已被拾取（全局唯一）。

關鍵代碼結構

struct Node { int x, y, num, k; };
queue outer;

void bfs(int sx, int sy, int k) {
    queue q;
    q.push({sx, sy, 0, k});
    visited[sx][sy] = 1;
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        if (map[cur.x][cur.y] == 'd') { flag = 1; return; }
        if (map[cur.x][cur.y] == '*' && !pro[cur.x][cur.y] && cur.k < K) {
            pro[cur.x][cur.y] = 1;
            outer.push({cur.x, cur.y, 0, cur.k + 1}); // 產生新外層狀態
        }
        for (int d=0; d<4; d++) {
            Node nxt = cur;
            nxt.x += dx[d]; nxt.y += dy[d]; nxt.num++;
            if (in_bound && !visited && map!='x' && nxt.num <= record[cur.k] && !pro) {
                visited[nxt.x][nxt.y] = 1; q.push(nxt);
            }
        }
    }
}

int main() {
    // 讀入地圖、record[]
    outer.push({start_x, start_y, 0, 0});
    while (!outer.empty()) {
        Node cur = outer.front(); outer.pop();
        memset(visited, 0, sizeof(visited));
        bfs(cur.x, cur.y, cur.k);
        if (flag) break;
    }
    // 輸出結果
}

狀態空間分析

道具數 ≤ 10，網格 ≤ 100×100。外層狀態 ≤ 道具數！內層 BFS 每次 O(MN)。總體可行。