【題解】Google Kick Start 2020 Round C – p2. Stable Wall

【題目敘述】https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff43/00000000003379bb

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int t, r, c, a[26][26], g[30][30], cnt[26], h[26];
char cc;
string ans;

int main() {
    cin >> t;
    for (int Case = 1; Case <= t; Case++){
        cin >> r >> c;
        memset(g, 0, sizeof(g));
        memset(cnt, 0, sizeof(cnt));
        memset(h, 0, sizeof(h));
        memset(a, 0, sizeof(a));
        for (int i = 0; i < r; i++){
            for (int j = 0; j < c; j++){
                cin >> cc;
                g[i][j] = cc-'A';
                h[cc-'A'] = 1;
            }
        }
        for (int j = 0; j < c; j++){
            for (int i = 1; i < r; i++){
                if (g[i][j] != g[i-1][j] && a[g[i-1][j]][g[i][j]] == 0){
                    a[g[i-1][j]][g[i][j]] = 1;
                    cnt[g[i-1][j]]++;
                }
            }
        }
        queue <int> q;
        for (int i = 0; i < 26; i++){
            if (cnt[i] == 0) q.push(i);
        }
        ans = "";
        while (!q.empty()){
            int now = q.front();
            q.pop();
            for (int i = 0; i < 26; i++){
                if (a[i][now] == 1){
                    a[i][now] = 0;
                    cnt[i]--;
                    if (cnt[i] == 0) q.push(i);
                }
            }
            ans += (char)('A'+now);
        }
        cout << "Case #" << Case << ": ";
        if (ans.length() != 26){
            cout << -1 << "\n";
            continue;
        }
        for (char i:ans){
            if (h[i-'A']) cout << i;
        }
        cout << "\n";
    }
}
分享本文 Share with friends