dodging lasers

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

const int N=3000;
int dp[2][N][N];
bool r[2][N],c[2][N];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m,k;
    cin>>n>>m>>k;

    int i,j,mx=1e9;
    for(i=0;i<n;i++)
    {
        r[0][i]=r[1][i]=false;
        for(j=0;j<m;j++)
        {
            c[0][j]=c[1][j]=false;
            dp[0][i][j]=dp[1][i][j]=mx;
        }
    }

    for(i=0;i<k;i++)
    {
        int u,v; char s;
        cin>>u>>v>>s;
        u--; v--; int ty=0;
        if(s=='C') ty=1;
        if(ty==0)
        {
            r[0][u]=true;
            c[1][v]=true;
        }
        else
        {
            r[1][u]=true;
            c[0][v]=true;
        }
    }

    dp[0][0][0]=0;
    queue<int> q;
    q.push(0); q.push(0); q.push(0);
    vector<pair<int,int>> d;
    d.push_back({0,-1}); d.push_back({-1,0}); d.push_back({1,0}); d.push_back({0,1});
    while(!q.empty())
    {
        int pc=q.front(); q.pop();
        int px=q.front(); q.pop();
        int py=q.front(); q.pop();
        for(auto di:d)
        {
            int tx=px+di.first,ty=py+di.second,cx=pc^1;
            if(tx>=0 && tx<n && ty>=0 && ty<m && !c[cx][ty] && !r[cx][tx] && dp[cx][tx][ty]==mx)
            {
                q.push(cx); q.push(tx); q.push(ty);
                dp[cx][tx][ty]=dp[pc][px][py]+1;
            }
        }
    }

    int ans=min(dp[0][n-1][m-1],dp[1][n-1][m-1]);
    if(ans==mx) ans=-1;
    cout<<ans<<"\n";
    return 0;
}