Problem: Example

Input

2 10 6
4 4 E
6 4 W


Output

2

Solution (in CPP):

Solution:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
#include <queue>

using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define ft first
#define sd second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;
typedef queue<int> QI;

const LL mod=1000000007;
LL powmod(LL a,LL b) {LL res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

int n,w,d,p[23];

struct node{
    int x,y,l,r,to;
    bool ab=true;
    void read(){
        int x1,y1;char c;
        scanf("%d%d %c",&x1,&y1,&c);
        x=x1;y=y1;if(c=='N')to=1;else if(c=='E')to=2;else if(c=='S')to=3;else to=4;
    }
    void work(){
        if(to==1){
            int s=d-y,yo=w-x;
            if(x>s)l=x-s;
            else l=p[4]+y+x;
            if(yo>s)r=x+s;
            else r=p[2]+(s-yo);
        }else if(to==2){
            int s=d-y,yo=w-x;
            if(yo>s)l=x+s;
            else l=p[2]+(s-yo);
            if(yo>y)r=p[3]+yo-y;
            else r=p[2]+s+yo;
        }else if(to==3){
            int s=d-y,yo=w-x;
            if(yo>y)l=p[3]+yo-y;
            else l=p[2]+s+yo;
            if(x>y)r=p[3]+yo+y;
            else r=p[4]+y-x;
        }else{
            int s=d-y,yo=w-x;
            if(x>y)l=p[3]+yo+y;
            else l=p[4]+y-x;
            if(x>s)r=x-s;
            else r=p[4]+y+x;
        }
        if(r<l)r+=w+w+d+d;
    }
}a[2333];

bool cmp(node x,node y){
    if(x.l==y.l)return x.r<y.r;
    else return x.l<y.l;
}

int work(int x){
    int now=-1,re=0;
    rep(i,x,n){
      //  cout<<"!!!"<<i<<a[i].ab<<endl;
        if(a[i].ab){
            if(now>=a[i].l && now<=a[i].r)continue;
            else now=a[i].r,re++;
        }
    }
    rep(i,0,x){
      //  cout<<"!!!"<<i<<a[i].ab<<endl;
        if(a[i].ab){
            if(now>=(a[i].l+w+w+d+d)&&now<=(a[i].r+w+w+d+d))continue;
            else now=a[i].r+w+w+d+d,re++;
        }
    }
    return re;
}

int main(){
    scanf("%d%d%d",&n,&w,&d);p[1]=0;p[2]=w;p[3]=w+d;p[4]=w+d+w;
    rep(i,0,n){a[i].read();a[i].work();}
    sort(a,a+n,cmp);
    int ans=23333;
    rep(i,0,n){
        rep(j,0,n){
            if(i==j)continue;
            if(a[i].ab && a[j].ab){
                if(a[i].l<=a[j].l && a[i].r>=a[j].r)a[i].ab=false;
                if(a[i].l<=(a[j].l+w+w+d+d)&&a[i].r>=(a[j].r+w+w+d+d))a[i].ab=false;
            }
        }
    }
    rep(i,0,n){
        ans=min(ans,work(i));
    }
   /* rep(i,0,n){
        if(a[i].ab)cout<<a[i].l<<' '<<a[i].r<<endl;
    }*/
    cout<<ans<<endl;
	return 0;
}