ZeroJudge E999: 巨額獎金 (Bonus)

某戀愛遊戲製作公司為了慶祝十周年，特別在網路上發布了一個遊戲，誰能通關拿到最佳結局，就能獲得新台幣一千萬的巨額獎金。遊戲的內容如下：

一個男孩遇見了心儀的對象，參賽者要幫助這個男孩在每個階段進行事件選擇，選擇後會進入下一個階段，然後再進行選擇 …… 直至結局階段。結局為何，取決於玩家所經歷的階段和事件。所有的結局中，只有一個路線能達成最佳結局。

礙於成本考量，公司決定對於每個報名的人收費。他們對收費的金額進行討論，最後討論出了一連串複雜的數學式子作為費用的計算公式，其中遊戲進行的總路線數是最關鍵的數值。你是公司的一名員工，你必須負責算出路線總數 R。

遊戲的設定如下：

  1. 遊戲共有 N 個階段，S0 為初始階段，SN－1 為結局階段。
  2. 對每個階段 Si，事件 Eij 會讓玩家進入到階段 Sj。
  3. 對於任意階段，玩家最多僅能經歷一次。即：不會有任何事件可以讓玩家回到曾經經歷過的階段。
  4. 不管中間的事件選擇是什麼，總是 S0 開始，SN－1 結束。
  5. 路線總數 R 不為 0。
  6. 不會有重複的重件（兩個階段至多只由一個事件連接）。
ZeroJudge E999 題目解說

以上圖為例，這個遊戲共有 7 個不同路線可以到達 SN－1。

範例測資

範例輸入範例輸出
每組測資第一列有兩個正整數 N 及 E，N 表示階段的數量，階段分別編號
0 至 N－1，E（S－1 <= E <= 2×S）為事件的數量。接著有 E 列，每列有兩個整數
i、j，表示階段 Si 存在事件 Eij 能讓玩家進入階段 Sj。		每組測資輸出一個正整數 R，為路線總數。
9 12
0 1
0 2
0 3
0 5
0 7
3 4
1 4
4 6
7 6
6 8
2 8
5 8		5
10 14
0 1
0 2
1 3
1 4
1 5
1 6
2 6
3 9
4 9
5 9
6 7
6 8
7 9
8 9		7
ZeroJudge E999 範例測資

解題思路

使用 BFS，並且使用 Map 來紀錄每一個點可以前往的點。宣告一個 ans 陣列預設為 0，並且將 ans[0] 設為 1。

在 BFS 中，將下一個點的 ans += 這個點的 ans。需要注意的是，要紀錄每一個點前面有幾個點需要先走過，每走到一個點的時候就將其前面的點的數量–，如果這個點前面的點都已經走完之後才將其作為下一次 BFS 的起點。

答案就是 ans[N-1]。

範例程式碼－ZeroJudge E999: 巨額獎金 (Bonus)

#include <iostream>
#include <vector>
#include <map>
using namespace std;

map<int, vector<int>>MAP;
map<int, int>ans, previous;

pair<int, int> p (const int a, const int b) {
    pair<int, int>tmp;
    tmp.first = a;
    tmp.second = b;
    return tmp;
}

void BFS(const vector<int>start) {
    if (start.size() == 0) return;
    vector<int>newStart;
    for (int i = 0; i<start.size(); i++) {
        const int current = start[i];
        for (int j = 0 ; j<MAP[current].size(); j++) {
            const int next = MAP[current][j];
            previous[next]--;
            ans[next] += ans[current];
            if (previous[next] == 0) newStart.push_back(next);
        }
    }
    BFS(newStart);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, E;
    cin >> N >> E;
    for (int i = 0; i<E; i++) {
        int a, b;
        cin >> a >> b;
        MAP[a].push_back(b);
        previous[b]++;
    }
    ans[0] = 1;
    vector<int>start;
    start.push_back(0);
    BFS(start);
    cout << ans[N-1] << "\n";
}

//ZeroJudge E999
//Dr. SeanXD

標籤

相關文章

發佈留言