AOJ 2178 Futon

Futon
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2178

問題概要

二次元座標上にn枚布団がおいてある。
布団は1×2の大きさである。
今、n人の人がその布団で寝る。
だれかの足のとなりに他人の頭がこないように寝ることができるか答えよ。

解法

BFS
一つのマス頭か足かどちらかにきめて、同じ布団の違う場所はその逆、
それ以外の隣り合う場所は同じ方向で配置していく。
となり合うものでまだ訪れてないものをキューにつめて一つづつ確定していく。
布団の管理はmapでやると良い。
非連続の布団がある場合のまた訪れてない布団の管理はsetでやる。
そうすると、全体のオーダーはnlognくらい。

ソース

#include<iostream>
#include<map>
#include<set>
#include<queue>

#define REP(i,b, n) for(int i = b; i<(int)n;i++)
#define rep(i, n) REP(i, 0, n)

using namespace std;

const int dx[] = {0, 1, 0, -1};
const int dy[] = {-1, 0, 1, 0};
enum{
 U, R, D, L
};
enum DIR{
 head, leg, non
};

class Futon{
public:
 DIR dir;
 int id;
 Futon(){
   dir = non;
 }
};

int main(){
 int n;
 while(cin >> n){
   if(n == 0)break;
   map<pair<int, int>, Futon > S;
   set<pair<int, int> > remain;
   rep(i, n){
     Futon tmp;
     pair<int, int> pos;
     cin >>pos.first >>pos.second;
     char d;
     cin >> d;
     tmp.id = i;
     S[pos] = tmp;
     remain.insert(pos);
     if(d == 'x'){
       pos.first += dx[R];
       pos.second += dy[R];
     }
     else {
       pos.first += dx[D];
       pos.second += dy[D];
     }
     S[pos] = tmp;
     remain.insert(pos);
   }
   string ans = "Yes";
   while(1){
     if(remain.size() == 0)break;
     pair<int, int> now = *(remain.begin());
     S[now].dir = head;
     remain.erase(remain.begin());
     queue<pair<int, int> > Q;
     Q.push(now);
     while(!Q.empty()){
       now = Q.front();
       Futon &fnow = S[now];
       Q.pop();
       rep(i, 4){
         pair<int, int> tmp = now;
         tmp.first += dx[i];
         tmp.second += dy[i];
         if(S.find(tmp) == S.end())continue;
         Futon &next = S[tmp];
         bool sameDir = next.dir == fnow.dir;
         bool sameId = next.id == fnow.id;
         if(next.dir != non){
           if( sameDir && sameId ){
             ans = "No";
             break;
           }
           if( !sameDir && !sameId ){
             ans = "No";
             break;
           }
           continue;
         }
         if( sameId ){
           if(fnow.dir == head)next.dir = leg;
           else next.dir = head;
         }
         else {
           next.dir = fnow.dir;
         }
         remain.erase(remain.find(tmp));
         Q.push(tmp);
       }
       if(ans == "No")break;
     }
     if(ans == "No")break;
   }
   cout << ans << endl;
 }
 return 0;
}