TOI10: Map

#include <bits/stdc++.h>

using namespace std;
using pii = pair<pair<int,int>,int>;

/*
    0 --> no edge
    1 --> left
    2 --> right
    3 --> up
    4 --> down
*/

vector<pair<int,int> > G[40005];
int MAP[205][205];
bool visited[40005],cvisited[40005];
map<int,pair<int,int> > M,CM;
pii mx = {{0,0},0};
int n,m;

void setmap(){
    M[1] = {0,1};
    M[2] = {0,-1};
    M[3] = {1,0};
    M[4] = {-1,0};
    CM[1] = {0,-1};
    CM[2] = {0,1};
    CM[3] = {-1,0};
    CM[4] = {1,0};
}

void dfs(int x,int y,int u){
    visited[u] = true;
    mx = max(mx,{{x,y},u});
    for(auto c : G[u]){
        if(!visited[c.first]){
            int vx = M[c.second].first;
            int vy = M[c.second].second;
            dfs(x+vx,y+vy,c.first);
        }
    }
}

void createmap(int x,int y,int u){
    cvisited[u] = true;
    MAP[x][y] = u;
    for(auto c : G[u]){
        if(!cvisited[c.first]){
            int vx = CM[c.second].first;
            int vy = CM[c.second].second;
            createmap(x+vx,y+vy,c.first);
        }
    }
}

void print(){
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            printf("%d ",MAP[i][j]);
        printf("\n");
    }
}


int main(){
    setmap();
    scanf("%d%d",&n,&m);
    for(int i=1;i<n*m;i++){
        int u,v;
        char d;
        scanf("%d %c %d",&u,&d,&v);
        if(d == 'L'){
            G[u].push_back({v,2});
            G[v].push_back({u,1});
        }
        else if(d == 'U'){
            G[u].push_back({v,4});
            G[v].push_back({u,3});
        }
    }
    dfs(0,0,0);
    int u = mx.second;
    createmap(0,0,u);
    print();
}