TOI15: Fly

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

typedef tuple<int, int, int, int> tpp;

const int R = 2000;
const int C = 500;

int posL[C + C][R + 2], posR[C + C][R + 2], row, col;
char dirL[R + 1], dirR[R + 1];
bool visited[R + 2][C + 2][C + C];

int dirToInt(char c){
    if(c == 'R'){
        return 1;
    }
    return -1;
}
int main(){

    scanf("%d%d", &row, &col);
    for(int i = 1; i <= row; ++i){
        char dirLeft, dirRight;
        scanf("%d %c%d %c", &posL[0][i], &dirL[i], &posR[0][i], &dirR[i]);
    }

    // Precompute trap state
    posL[0][0] = 0;
    posR[0][0] = col;
    posL[0][row + 1] = 0;
    posR[0][row + 1] = col;
    for(int t = 1; t < col + col; ++t){
        posL[t][0] = 0;
        posR[t][0] = col;
        posL[t][row + 1] = 0;
        posR[t][row + 1] = col;
        for(int i = 1; i <= row; ++i){
            if(posL[t - 1][i] + 1 == posR[t - 1][i] && dirL[i] == 'R' && dirR[i] == 'L'){
                posL[t][i] = posL[t - 1][i];
                posR[t][i] = posR[t - 1][i];
                dirL[i] = 'L';
                dirR[i] = 'R';
                continue;
            } else if(posL[t - 1][i] == posR[t - 1][i] && dirL[i] == 'R' && dirR[i] == 'L'){
                posL[t][i] = posL[t - 1][i] - 1;
                posR[t][i] = posR[t - 1][i] + 1;
                dirL[i] = 'L';
                dirR[i] = 'R';
                continue;
            }
            if(posL[t - 1][i] == 0 && dirL[i] == 'L'){
                posL[t][i] = 1;
                dirL[i] = 'R';
            } else {
                posL[t][i] = posL[t - 1][i] + dirToInt(dirL[i]);
            }
            if(posR[t - 1][i] == col && dirR[i] == 'R'){
                posR[t][i] = col - 1;
                dirR[i] = 'L';
            } else {
                posR[t][i] = posR[t - 1][i] + dirToInt(dirR[i]);
            }
        }
    }

    queue<tpp> que; // tpp(dist, row, col, state)
    for(int i = 1; i < col; ++i){
        visited[0][i][0] = true;
        que.emplace(0, 0, i, 0);
    }
    int mxTime = (row + 1) * (col + col - 1);
    for(int t = 0; t <= mxTime; ++t){
        while(!que.empty() && get<0>(que.front()) == t){
            int d = get<0>(que.front());
            int ur = get<1>(que.front());
            int uc = get<2>(que.front());
            int us = get<3>(que.front());
            que.pop();
            if(uc <= posL[us][ur] || uc >= posR[us][ur]){
                continue;
            }
            if(ur == row + 1){
                cout << d;
                return 0;
            }
            int vs = (us + 1) % (col + col);
            if(!visited[ur + 1][uc][vs]){
                visited[ur + 1][uc][vs] = true;
                que.emplace(d + 1, ur + 1, uc, vs);
            }
            if(!visited[ur][uc][vs]){
                visited[ur][uc][vs] = true;
                que.emplace(d + 1, ur, uc, vs);
            }
        }
    }

    return 0;
}