Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

int main() {
    int n, w, d;
    cin >> n >> w >> d;
    vector<pii> v;
    for(int i=0; i<n; ++i) {
        int x, y;
        char f;
        cin >> x >> y >> f;
        if(f == 'W') {
            v.emplace_back(x + y, -x + y);
        } else if(f == 'N') {
            v.emplace_back(2*d + x - y, x + y);
        } else if(f == 'E') {
            v.emplace_back(2*(d+w) - x - y, 2*d + x - y);
        } else {
            v.emplace_back(2*(d+w) - x + y ,2*(d+w) - x - y);
        }
    }
    sort(v.begin(), v.end());
    int L = 2*(w + d);
    int res = 1e9;
    for(int i=0; i<n; ++i) {
        auto tmp = v;
        for(int j=i-1; j>=0; --j) {
            if(tmp[j].first < tmp[i].first) {
                tmp[j].first += L;
                tmp[j].second += L;
            }
        }
        sort(tmp.begin(), tmp.end());
        int cnt = 1;
        int now = tmp[0].first;
        for(int j=0; j<n; ++j) {
            if(tmp[j].second > now) {
                now = tmp[j].first;
                cnt++;
            }
        }
        res = min(res, cnt);
    }
    cout << res << endl;
}