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

aoj2178.cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(_v) for(auto _x:_v){cout<<_x<<" ";}cout<<endl
#define printVS(_vs) for(auto _x : _vs){cout << _x << endl;}
#define printVV(_vv) for(auto _v:_vv){for(auto _x:_v){cout<<_x<<" ";}cout<<endl;}
#define printP(_p) cout << _p.first << " " << _p.second << endl
#define printVP(_vp) for(auto _p : _vp) printP(_p);

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;

struct Point {
    int x, y, id;
    Point(){}
    Point(int _x, int _y, int _id) : x(_x), y(_y), id(_id) {}
};

bool cmp_Yx(const Point& p, const Point& q) {
    if (p.y != q.y) return p.y < q.y;
    if (p.x != q.x) return p.x < q.x;
    assert(false);
}

bool cmp_Xy(const Point& p, const Point& q) {
    if (p.x != q.x) return p.x < q.x;
    if (p.y != q.y) return p.y < q.y;
    assert(false);
}

bool adjecent(const Point& p, const Point& q) {
    if (p.x == q.x && abs(p.y - q.y) == 1) return true;
    if (p.y == q.y && abs(p.x - q.x) == 1) return true;
    return false;
}

// undirected
void addEdge(Graph& G, int x, int y) {
    G[x].emplace_back(y);
    G[y].emplace_back(x);
}

void solve(int n) {
    vector<Point> p;
    rep(i, n) {
        int x, y;
        char dir;
        cin >> x >> y >> dir;
        p.emplace_back(x, y, 2 * i);
        if (dir == 'x') {
            p.emplace_back(x + 1, y, 2 * i + 1);
        } else {
            p.emplace_back(x, y + 1, 2 * i + 1);
        }
    }

    Graph G(2 * n);

    // horizontal edge
    sort(all(p), cmp_Yx);
    rep(i, 2 * n - 1) {
        if (p[i].y == p[i + 1].y && p[i + 1].x - p[i].x == 1) {
            addEdge(G, p[i].id, p[i + 1].id);
        }
    }

    // vertical edge
    sort(all(p), cmp_Xy);
    rep(i, 2 * n - 1) {
        if (p[i].x == p[i + 1].x && p[i + 1].y - p[i].y == 1) {
            addEdge(G, p[i].id, p[i + 1].id);
        }
    }

    vector<int> color(2 * n, -1);

    std::function<bool(int,int)> dfs = [&](int i, int c) {
        color[i] = c;

        for (auto j : G[i]) {
            if (color[j] == -1) continue;
            if (i / 2 == j / 2 && color[i] == color[j]) {
                // same futon but same color
                return false;
            }
            if (i / 2 != j / 2 && color[i] != color[j]) {
                // adjecent cells in different futons but different color
                return false;
            }
        }

        for (auto j : G[i]) {
            if (color[j] != -1) continue;
            if (i / 2 == j / 2) {
                // same futon
                if (!dfs(j, c^1)) {
                    return false;
                }
            } else {
                // other futon
                if (!dfs(j, c)) {
                    return false;
                }
            }
        }

        return true;
    };

    rep(i, 2 * n) {
        if (color[i] == -1 && !dfs(i, 0)) {
            cout << "No" << endl;
            return;
        }
    }

    cout << "Yes" << endl;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n;
    while (cin >> n, n) {
        solve(n);
    }
}