C.cpp

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

int main(){
    int n, m, c;
    cin >> n >> m >> c;

    // Cars[0] will be n position
    // Cars[1] will be m position
    // Cars[2] will be direction
    // Cars[3] will be a flag if collide
    vector<vector<int> > cars(c, vector<int>(4));
    vector<vector<int> > crossings(n, vector<int>(m, -1));

    for(int i = 0; i < c; i++){
        int a, b;
        char d;
        cin >> a >> b >> d;
        a--;
        b--;
        crossings[a][b] = i;
        cars[i][0] = a;
        cars[i][1] = b;
        cars[i][2] = int(d);
        cars[i][3] = 0;
    }

    bool movedSomething = true;
    int notCollide = c;

    while(movedSomething && notCollide){
        movedSomething = false;
        vector<vector<int> > copyCrossings(n, vector<int>(m, -1));
        for(int i = 0; i < c; i++){
            if(!cars[i][3]){
                switch(cars[i][2]){
                    case 'N': {
                        if(cars[i][0] >= 0){
                            cars[i][0]--;
                            if(cars[i][0] >= 0){
                                if(copyCrossings[cars[i][0]][cars[i][1]] > -1) {
                                    notCollide--;
                                    if(!cars[crossings[cars[i][0]][cars[i][1]]][3]){
                                        notCollide--;
                                        cars[crossings[cars[i][0]][cars[i][1]]][3] = 1;
                                    }
                                    cars[i][3] = 1;
                                }
                                copyCrossings[cars[i][0]][cars[i][1]] = i;
                                if(cars[i][0] + 2 <= n - 1 && crossings[cars[i][0]][cars[i][1]] > -1){
                                    if(copyCrossings[cars[i][0] + 2][cars[i][1]] > -1){
                                        notCollide -= 2;
                                        cars[i][3] = 1;
                                        cars[crossings[cars[i][0]][cars[i][1]]][3] = 1;
                                    }
                                }
                            }
                            movedSomething = true;
                        }
                    }
                    break;
                    case 'S': {
                        if(cars[i][0] >= n - 1){
                            cars[i][0]++;
                            if(cars[i][0] >= n - 1){
                                if(copyCrossings[cars[i][0]][cars[i][1]] > -1) {
                                    notCollide--;
                                    if(!cars[crossings[cars[i][0]][cars[i][1]]][3]){
                                        notCollide--;
                                        cars[crossings[cars[i][0]][cars[i][1]]][3] = 1;
                                    }
                                    cars[i][3] = 1;
                                }
                                copyCrossings[cars[i][0]][cars[i][1]] = i;
                                if(crossings[cars[i][0]][cars[i][1]] > -1){
                                    if(cars[i][0] - 2 >= 0 && copyCrossings[cars[i][0] - 2][cars[i][1]] > -1){
                                        notCollide -= 2;
                                        cars[i][3] = 1;
                                        cars[crossings[cars[i][0]][cars[i][1]]][3] = 1;
                                        copyCrossings[cars[i][0]][cars[i][1]] = -1;
                                        copyCrossings[cars[i][0] - 1][cars[i][1]] = i;
                                    }
                                }
                            }
                            movedSomething = true;
                        }
                    }
                    break;
                    case 'L': {
                        if(cars[i][1] >= m - 1){
                            cars[i][1]++;
                            if(cars[i][1] >= m -1){
                                if(copyCrossings[cars[i][0]][cars[i][1]] > -1) {
                                    notCollide--;
                                    if(!cars[crossings[cars[i][0]][cars[i][1]]][3]){
                                        notCollide--;
                                        cars[crossings[cars[i][0]][cars[i][1]]][3] = 1;
                                    }
                                    cars[i][3] = 1;
                                }
                                copyCrossings[cars[i][0]][cars[i][1]] = i;
                                if(crossings[cars[i][0]][cars[i][1]] > -1){
                                    if(cars[i][1] - 2 >= 0 && copyCrossings[cars[i][0]][cars[i][1] - 2] > -1){
                                        notCollide -= 2;
                                        cars[i][3] = 1;
                                        cars[crossings[cars[i][0]][cars[i][1]]][3] = 1;
                                    }
                                }
                            }
                            movedSomething = true;
                        }
                    }
                    break;
                    case 'O': {
                        if(cars[i][1] >= 0){
                            cars[i][1]--;
                            if(cars[i][1] >= 0){
                                if(copyCrossings[cars[i][0]][cars[i][1]] > -1) {
                                    notCollide--;
                                    if(!cars[crossings[cars[i][0]][cars[i][1]]][3]){
                                        notCollide--;
                                        cars[crossings[cars[i][0]][cars[i][1]]][3] = 1;
                                    }
                                    cars[i][3] = 1;
                                }
                                copyCrossings[cars[i][0]][cars[i][1]] = i;
                                if(crossings[cars[i][0]][cars[i][1]] > -1){
                                    if(cars[i][1] + 2 >= m - 1 && copyCrossings[cars[i][0]][cars[i][1] + 2] > -1){
                                        notCollide -= 2;
                                        cars[i][3] = 1;
                                        cars[crossings[cars[i][0]][cars[i][1]]][3] = 1;
                                        copyCrossings[cars[i][0]][cars[i][1]] = -1;
                                        copyCrossings[cars[i][0]][cars[i][1] + 1] = i;
                                    }
                                }
                            }
                            movedSomething = true;
                        }
                    }
                    break;
                }
            } else {
                copyCrossings[cars[i][0]][cars[i][1]] = i;
            }
        }
        crossings = copyCrossings;
    }

    cout << notCollide << endl;
}