TOI10: Map

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

#define pii pair<int, int>
#define f first
#define s second

int main(){

    int row, col;
    scanf("%d", &row);
    scanf("%d", &col);
    vector<vector<int>> adj(row * col, vector<int>(4, -1)); // 0=U 1=R 2=D 3=L

    int loop = row * col - 1;
    for(int i = 1; i <= loop; ++i){
        int u, v;
        char cmd;
        scanf("%d", &u);
        scanf(" %c", &cmd);
        scanf("%d", &v);
        if(cmd == 'U'){
            adj[u][2] = v;
            adj[v][0] = u;
        } else if(cmd == 'L'){
            adj[u][1] = v;
            adj[v][3] = u;
        }
    }

    /// BFS
    int mnr = 0;
    int mnc = 0;
    vector<pii> dist(row * col, {0, 0});
    queue<int> q;
    q.push(0);
    dist[0] = {0, 0};
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = 0; i < 4; ++i){
            int v = adj[u][i];
            if(v != -1 && dist[v] == make_pair(0, 0)){
                switch(i){
                case 0: // Up
                    dist[v] = {dist[u].f - 1, dist[u].s};
                    break;
                case 1: // Right
                    dist[v] = {dist[u].f, dist[u].s + 1};
                    break;
                case 2: // Down
                    dist[v] = {dist[u].f + 1, dist[u].s};
                    break;
                case 3: // Left
                    dist[v] = {dist[u].f, dist[u].s - 1};
                    break;
                }
                mnr = min(mnr, dist[v].f);
                mnc = min(mnc, dist[v].s);
                q.push(v);
            }
        }
    }

    vector<vector<int>> mp(row + 1, vector<int>(col + 1, 0));
    for(int i = 0; i <= loop; ++i){
        mp[dist[i].f - mnr][dist[i].s - mnc] = i;
    }

    for(int i = 0; i < row; ++i){
        for(int j = 0; j < col; ++j){
            cout << mp[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}