AOJ 2178 : Futon
問題リンク:Futon | Aizu Online Judge
問題概要:
n枚の布団の位置情報が与えられる
それらの布団に人が寝るわけだが、
人の頭のに隣接する部分に他の人の足があってはならない
そのような寝方があるかどうか判定せよ
解法:
グラフを構築して2色でそれらのノードを塗れるかどうか判定する
あるノードに白を塗った場合、そのノードに隣接するノードは全て黒でなければならない といった感じで全て塗っていく
その様に塗れない場合は"No"
塗れる場合は"Yes"となる
実装時間:
1時間8分
コード:
#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; }