// 2009模擬地区予選 D : Futon #include #include #include #include #include using namespace std; char dx[] = {1,0,-1,0}; char dy[] = {0,1,0,-1}; int main(){ int n; int color[40000]; while(cin >> n, n){ int x, y; char c; // ふとんがしいてある座標集合 vector< pair > vp; // 座標 -> インデックス を持つマップ map< pair, int > futon; for(int i=0;i> x >> y >> c; vp.push_back(make_pair(x ,y )); vp.push_back(make_pair(x+(c=='x'),y+(c=='y'))); futon.insert(make_pair(vp[2*i ],2*i )); futon.insert(make_pair(vp[2*i+1],2*i+1)); } // -1 : 未訪問,0 : 頭, 1 : 足 memset(color,-1,sizeof(color)); // 制約に反しない配置が可能か bool flag = true; map< pair, int >::iterator it; for(it=futon.begin();it!=futon.end()&&flag;it++){ if(color[(*it).second]!=-1) continue; // 現在地を頭と仮定 color[(*it).second] = 0; // 幅優先で周囲の配置を決めていく queue qu; qu.push((*it).second); while(!qu.empty()&&flag){ int pos = qu.front(); qu.pop(); int x = vp[pos].first, y = vp[pos].second; for(int i=0;i<4;i++){ int nx = x+dx[i], ny = y+dy[i]; // 現在地の4近傍にふとんが存在 if(futon.count(make_pair(nx,ny)) != 0){ int next = futon[make_pair(nx,ny)]; // next/2 = pos/2なら同じふとんなので,頭・足は逆転する if(color[next]!=-1){ // 条件に反する配置が既にされていたらアウト if(color[next] != (color[pos]+(next/2==pos/2))%2) flag = false; } else { color[next] = (color[pos]+(next/2==pos/2))%2; qu.push(next); } } } } } cout << (flag ? "Yes" : "No") << endl; } }