SRM 533 div1 med: MagicBoard

問題

TopCoder Statistics - Problem Statement

解法

見た目がハミルトンパスに見えますが, 実はオイラー路の問題になります。

蟻本の p205 に書いてあるようなグラフを作るようなイメージです。二部グラフ (U, W) を作るのですが, board[i][j] == '#' ならば, U の i 番目の頂点と, W の j 番目の頂点の間に辺を貼ります。

そうすると, 例えば「場所 (r, c0) から (r, c1) に移動する」というのは, W の c0 番目の頂点から U の r 番目の頂点に移動し, W の c1 番目の頂点に移動する, ということになります。
このようにグラフを表現すると,

• すべての '#' を通らなければならない -> 二部グラフ (U, W) のすべての辺を通らなければならない(つまりオイラー路があるかを判定したい)
• 偶数番目は横移動, 奇数番目は縦移動 -> (これも二部グラフであることと関連)オイラー路のはじめの頂点は W 側からはじめなければならない

となります。

struct UnionFind {
    vector<int> par;
    int n, cnt;
    UnionFind(const int& x = 0) {init(x);}
    void init(const int& x) {par.assign(cnt=n=x, -1);}
    inline int find(const int& x) {return par[x] < 0 ? x : par[x] = find(par[x]);}
    inline bool same(const int& x, const int& y) {return find(x) == find(y);}
    inline bool unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return false;
        --cnt;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    inline int count() const {return cnt;}
    inline int count(int x) {return -par[find(x)];}
};

class MagicBoard {
public:
    string ableToUnlock(vector <string> board) {
        const string yes = "YES", no = "NO";
        int n = board.size(), m = board[0].size();
        UnionFind uf(n+m);
        vector<vi> G(n+m);
        int memo = 0;
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
            if (board[i][j] == '#') {
                G[i].push_back(j+n);
                G[j+n].push_back(i);
                uf.unite(i, j+n);
                memo = i;
            }
        }
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
            if (board[i][j] == '#' && !uf.same(memo, i)) return no;
        }
        int cntr = 0, cntc = 0;
        for (int i = 0; i < n+m; i++) {
            if (G[i].size()%2) {
                if (i < n) cntr++;
                else cntc++;
            }
        }
        if (cntc+cntr == 0 || cntc+cntr == 2) {
            if (cntr < 2) return yes;
            else return no;
        }
        return no;
    }
};