Atcoder Grand Contest 017 E. Jigsaw

Atcoder Grand Contest 017 E. Jigsaw

E: Jigsaw - AtCoder Grand Contest 017 | AtCoder

感想

新しい感じのdfsをした。

解法

まずある右（左）の形状に対して、対応する左（右）の形状が一意に定まることに注意する。このうまくフィットする形状同士を同一の値（形状が変わる高さ）で管理する。ただし、左右のどちらの形状で何回現れたのかは記録しておく。同じブロックの左右の形状についてその値同士で辺を張っておく。

さて、まず、ある形状の値について床につかないようなパーツの方が多くなっていればこの時点で構成不可能である。逆に、床につくパーツの方が多い分には全く問題ない。なぜなら、そのようなパーツは端っことして使えるからである。この問題では完成したブロックの連結成分が1個でなくてもよいことに注意すること。

次に、この接合部分に関する（各個別の部分、ではなく）dfsをする。言い換えると、すべての同一形状の接合部分は一気に探索する。そして、逐一その個数に関するチェックをし、端っこのパーツをうまく決めれるかどうかをみる。

説明が全然できてない感じがするけど...

実装

#include "bits/stdc++.h"
using namespace std;

vector<int> g[505];
int l_cnt[505], r_cnt[505];
bool used[505];

int print(bool ok) {
        if (ok) cout << "YES" << endl;
        else cout << "NO" << endl;
        return 0;
}

bool dfs(int v) {
        used[v] = true;
        bool res = l_cnt[v] != r_cnt[v];
        for (auto u : g[v]) if (!used[u]) res |= dfs(u);
        return res;
}

int main() {      
        int n, h, a, b, c, d;
        cin >> n >> h;
        for (int i = 0; i < n; i ++) {
                cin >> a >> b >> c >> d;
                int lh = (c == 0 ? a : c + 250);
                int rh = (d == 0 ? b + 250 : d);
                l_cnt[lh] ++;
                r_cnt[rh] ++;
                g[lh].push_back(rh);
                g[rh].push_back(lh);
        }
        for (int i = 0; i < h + 1; i ++) if (r_cnt[i] > l_cnt[i]) return print(0);
        for (int i = 251; i < h + 251; i ++) if (l_cnt[i] > r_cnt[i]) return print(0);
        for (int i = 0; i < 501; i ++) if (!used[i]) if (!g[i].empty()) if (!dfs(i)) return print(0);
        return print(1);
}