TOI10: Map

#include <bits/stdc++.h>
using namespace std;
int up[40010],down[40010],l[40010],r[40010];
int ar[210][210];
int n,m;
using pi = pair<int,int> ;
using pii = pair<int,pi> ;
void fill_ar(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ar[i][j]=0;
        }
    }
}
bool check_ar(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(ar[i][j]==0) return false;
        }
    }
    return true;
}
bool position(int i,int j){
    return i>=1 and i<=n and j>=1 and j<=m and ar[i][j]==0;
}
void bfs(int x){
    queue <pii> q;
    q.push({x,{1,1}});

    while(q.size()>0){

        int ui,uj;
        x=q.front().first;
        ui=q.front().second.first;
        uj=q.front().second.second;
        ar[ui][uj]=x;
        q.pop();

        if(l[x]!=0 and position(ui,uj-1)) q.push({l[x],{ui,uj-1}});
        if(r[x]!=0 and position(ui,uj+1)) q.push({r[x],{ui,uj+1} });
        if(up[x]!=0 and position(ui-1,uj)) q.push({up[x],{ui-1,uj}});
        if(down[x]!=0 and position(ui+1,uj)) q.push({down[x],{ui+1,uj}});
    }
}
int main(){

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n*m-1;i++){
        int a,b;
        char opr;
        scanf("%d %c %d",&a,&opr,&b);
        a++;
        b++;
        if(opr=='U'){
            up[b]=a;
            down[a]=b;
        }
        else if(opr=='L'){
            l[b]=a;
            r[a]=b;
        }
    }


    for(int i=1;i<=n*m;i++){
        if(up[i]==0 and l[i]==0) {
            bfs(i);
            if(check_ar()) break;
            else fill_ar();
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            printf("%d ",ar[i][j]-1);
        }
        printf("\n");
    }


    return 0;
}
/*

3 3
1 U 2
5 L 1
0 L 4
8 L 5
4 L 7
3 L 6
8 U 3
2 U 7

8 5 1
3 6 2
0 4 7

*/