【題解】TIOJ 1092 . A.跳格子遊戲

【題目敘述】https://tioj.ck.tp.edu.tw/problems/1092
【解題想法】反向(?)拓撲排序 (Topological sorting)

  • 舉例如下圖,9個圓圈,編號1到9,並規定1號圓圈是起點、9號是終點。走到9號圓圈者為贏家。
  • 有箭頭從 a 指向 b時,表示b的上一層有a,pre[b] = a。
  • a的「出邊」要多加一條,out[a]++。
  • 下圖8號圓圈的「出邊」只有一條,因此可以決定走到8號圓圈者為輸家。
  • 由此類推,走到6號圓圈和7號圓圈者為贏家。
  • 繼續類推到1號圓圈,可以知道先開始的人贏或輸。
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int maxn = 1e4;
int n, e, out[maxn], winner[maxn], now, a, b;
vector <int> pre[maxn];
string player1;

int main() {
    while (cin >> n >> e){
        if (n == 0 && e == 0) break;
        memset(out, 0, sizeof(out));
        memset(winner, 0, sizeof(winner));
        for (int i = 0; i < n; i++){
            pre[i].clear();
        }
        for (int i = 0; i < e; i++){
            cin >> a >> b;
            pre[b-1].push_back(a-1);
            out[a-1]++;
        }
        queue <int> q;
        q.push(n-1);
        winner[n-1] = 0;
        while (!q.empty()){
            now = q.front();
            q.pop();
            for (int i:pre[now]){
                out[i]--;
                if (winner[now] == 0) winner[i] = 1;
                if (out[i] == 0) q.push(i);
            }
        }
        cin >> player1;
        if (player1 == "Mimi") winner[0] ^= 1;
        if (winner[0]) cout << "Mimi\n";
        else cout << "Moumou\n";
    }
    return 0;
}
分享本文 Share with friends