AOJ 2178 : Futon

問題リンク：Futon | Aizu Online Judge

問題概要：
n枚の布団の位置情報が与えられる
それらの布団に人が寝るわけだが、
人の頭のに隣接する部分に他の人の足があってはならない
そのような寝方があるかどうか判定せよ

解法：
グラフを構築して2色でそれらのノードを塗れるかどうか判定する
あるノードに白を塗った場合、そのノードに隣接するノードは全て黒でなければならない　といった感じで全て塗っていく
その様に塗れない場合は"No"
塗れる場合は"Yes"となる

実装時間：
1時間８分

コード：

#include<algorithm>
#include<vector>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
#include<climits>
#include<cassert>
#include<deque>

#define MAX 20010
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)

using namespace std;

struct Point{
  int x,y;
  char c;
  Point(int x=IINF,int y=IINF,char c='$'):x(x),y(y),c(c){}
  bool operator < (const Point& a)const{
    return ( (x!=a.x) ? (x < a.x) : (y < a.y) );
  }
};

int n;
vector<int> G[MAX];
char color[MAX];

inline void makeGraph(const vector<Point>& vec,map<Point,int>& Index){
  rep(i,n)G[i].clear();
  rep(i,vec.size()){
    Point p1 = vec[i];
    Point p2 = p1;
    assert(Index.find(vec[i]) != Index.end());
    int cur = Index[vec[i]];
    if(p1.c == 'x')p2.x++;
    else if(p1.c == 'y')p2.y++;
    else assert(false);
    //cout << "Futon( (" << p1.x << "," << p1.y << ") , (" << p2.x << "," << p2.y << ") )" << endl;

    for(int y=p1.y-1;y<=p2.y+1;y++){
      for(int x=p1.x-1;x<=p2.x+1;x++){
	if(x == p1.x-1 && y == p1.y-1)continue;
	if(x == p2.x+1 && y == p1.y-1)continue;
	if(x == p1.x-1 && y == p2.y+1)continue;
	if(x == p2.x+1 && y == p2.y+1)continue;
	//cout << "check => (" << x << "," << y << ")" << endl;
	if(Index.find(Point(x,y)) != Index.end()){

	  int next = Index[Point(x,y)];
	  if(cur == next)continue;

	  G[cur].push_back(next);
	}
      }
    }
  }

  rep(i,n){
    sort(G[i].begin(),G[i].end());
    G[i].erase(unique(G[i].begin(),G[i].end()),G[i].end());
  }
}

bool dfs(int cur,char c){
  color[cur] = c;
  char rec = ((c == 'w')?'b':'w');
  for(int i=0;i<G[cur].size();i++){
    if(color[G[cur][i]] == c)return false;
    if(color[G[cur][i]] == 'x' && !dfs(G[cur][i],rec))return false;
  }
  return true;
}

int main(){

  while(cin >> n,n){
    // out = false;
    map<Point,int> Index;
    vector<Point> input;
    int dex = 0;
    for(int i=0;i<n;i++){
      int x,y;
      char c;
      cin >> x >> y >> c;
      Point p;
      if(c == 'x'){
	p = Point(x+1,y);
      } else {
	p = Point(x,y+1);
      }
      input.push_back(Point(x,y,c));
      Index[Point(x,y)] = Index[p]= dex++;
      color[i] = 'x';
    }
    assert(dex == n);
    makeGraph(input,Index);

    for(int i=0;i<n;i++){
      if(color[i] == 'x'){
	if(!dfs(i,'w')){
	  cout << "No" << endl;
	  goto Fin;
	}
      }
    }
    cout << "Yes" << endl;
  Fin:;


  }
  return 0;
}