AOJ2178 Futon

問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2534

N個の2*1マスの布団を広大なグリッド上に並べる。各々左上の座標と、縦と横のどちらの向きで配置するかの情報が与えられている。別の人の頭と足が隣り合わせになってしまう箇所が１つでも有れば、悪い配置となる。そうでなければ良い配置である。
良い配置かどうか判定せよ。
N <= 20000
座標は10^9以下

解説
布団の2マスと隣接する布団のマスとの間にグラフを張る。頭と足とで、同じものか違うものかの制限があるので、グラフの辺にその情報を加える。よって辺の情報は(隣接するマス, 同じか反対か)というようにすれば良い。
各連結成分ごとに、ある1つの頂点を頭か足か決め打ちしてDFSしたときに良い配置の方法で矛盾が生じないかを判定する。つまり、一度"頭"とメモしたところが、探索を進めて別の頂点から戻ってきたときに"足"とメモされる場合、矛盾となる。

別解として、Unionfindでグリッドグラフを連結してやる方法もあると思うが、自分は下手なやり方だったのでTLEしてしまった。再考察の必要がある。

int const OppoSide = 0;
int const SameSide = 1;
 
int N;
vector<pair<int, int>> G[44444];
map<pair<int, int>, int> MP;
map<int, pair<int, int>> CD;
int vis[44444];
 
bool dfs(int curr, int col) {
  for(auto& e: G[curr]) {
    int next, dir; tie(next, dir) = e;
    int nextCol = dir == OppoSide ? col ^ 1 : col;
    if(vis[next] + 1) {
      if(vis[next] != nextCol) return false;
    } else {
      vis[next] = nextCol;
      if(!dfs(next, nextCol)) return false;
    }
  }
  return true;
}
 
int main() {
 
  for(int M; cin >> M && M;) {
    vector<int> xs, ys;
    vector<int> X, Y; vector<char> D;
    rep(i, M) {
      int x, y; char d; cin >> x >> y >> d;
      X.push_back(x), Y.push_back(y), D.push_back(d);
 
      xs.push_back(x-1),  ys.push_back(y-1);
      xs.push_back(x),    ys.push_back(y);
      xs.push_back(x+1),  ys.push_back(y+1);
 
      if(d == 'x') {
        xs.push_back(x+2);
      } else {
        ys.push_back(y+2);
      }
 
    }
 
    sort(all(xs)); xs.erase(unique(all(xs)), xs.end());
    sort(all(ys)); ys.erase(unique(all(ys)), ys.end());
 
    vector<int> NX, NY;
    rep(i, X.size()) {
      NX.push_back(lower_bound(all(xs), X[i]) - X.begin());
    }
    rep(i, Y.size()) {
      NY.push_back(lower_bound(all(ys), Y[i]) - Y.begin());
    }
    X = NX, Y = NY;
 
    MP.clear(), CD.clear();
    rep(i, 44444) G[i].clear();
    N = 0;
 
    rep(i, X.size()) {
      MP[make_pair(Y[i], X[i])] = N;
      CD[N++] = make_pair(Y[i], X[i]);
      if(D[i] == 'x') {
        MP[make_pair(Y[i], X[i]+1)] = N;
        CD[N] = make_pair(Y[i], X[i]+1);
        G[N-1].emplace_back(N, OppoSide), G[N].emplace_back(N-1, OppoSide);
        N++;
      } else {
        MP[make_pair(Y[i]+1, X[i])] = N;
        CD[N] = make_pair(Y[i]+1, X[i]);
        G[N-1].emplace_back(N, OppoSide), G[N].emplace_back(N-1, OppoSide);
        N++;
      }
    }
 
    rep(i, N) {
      auto curr = CD[i];
      rep(k, 4) {
        auto next = make_pair(CD[i].first + dy[k], CD[i].second + dx[k]);
        if(MP.find(next) == MP.end()) continue;
        G[i].emplace_back(MP[next], SameSide);
      }
    }
 
    minus(vis);
 
    bool ok = 1;
 
    rep(i, N) {
      if(vis[i] < 0) {
        vis[i] = 0;
        if(!dfs(i, 0)) {
          ok = 0;
          break;
        }
      }
    }
 
    cout << (ok ? "Yes" : "No") << endl;
 
  }
  return 0;
}