ZOJ 2849 Attack of Panda Virus：優先隊列 + BFS 模擬病毒傳播

問題建模

N×M 網格每格一台電腦，值為負數表示抵禦天數（-k 表示能抵禦 k 天）。初始有兩類病毒（類型 1~1000），類型值小者優先傳播。第 d 天只能感染抵禦 ≤ d 天的電腦。已感染電腦不阻擋傳播但不被重複感染。最終回答 Q 個查詢：每類病毒感染總數。

核心思路：優先隊列狀態擴展

• 狀態：(level, type, x, y)，其中 level 為當前天數（負值表示尚未達到抵禦要求），type 為病毒類型。
• 優先級：level 小者優先（天數早）；同 level 則 type 小者優先。
• 擴展：從隊列取出狀態，嘗試感染四鄰域。若目標未被感染且 grid[x][y] + level >= 0（抵禦天數 ≤ 當前天數），則感染成功，記錄答案，推入新狀態 (level, type, nx, ny)。否則記錄該方向所需最小 level（即 -grid[nx][ny]），稍後將當前狀態更新 level 後重新入隊等待。

關鍵代碼片段

struct Node {
    int level, type, x, y;
    bool operator<(const Node& o) const {
        if (level != o.level) return level > o.level; // 小頂堆
        return type > o.type;
    }
};
priority_queue q;
// 初始：將兩個初始病毒位置 level=1 入隊
while (!q.empty()) {
    Node cur = q.top(); q.pop();
    int tmp = -INF;
    for (int dir = 0; dir < 4; dir++) {
        int nx = cur.x + dx[dir], ny = cur.y + dy[dir];
        if (out of bounds || mp[nx][ny] > 0) continue; // 已感染
        if (mp[nx][ny] + cur.level >= 0) { // 可感染
            mp[nx][ny] = cur.type;
            ans[cur.type]++;
            q.push({cur.level, cur.type, nx, ny});
        } else {
            tmp = max(tmp, mp[nx][ny]); // 記錄最難感染的鄰居
        }
    }
    if (tmp != -INF) { // 有鄰居暫時不可感染
        q.push({-tmp, cur.type, cur.x, cur.y}); // 更新 level 後重試
    }
}

陷阱與優化

• Q 範圍未給明確上限，需開大數組（如 5e6）避免 RE。
• 病毒類型高達 1000，非僅 1,2。
• 網格 500×500，優先隊列狀態數可控，3000ms 時限內可通過。