Advertisement
YEZAELP

TOI10: Map

Jul 11th, 2020
77
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.84 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int up[40010],down[40010],l[40010],r[40010];
  4. int ar[210][210];
  5. int n,m;
  6. using pi = pair<int,int> ;
  7. using pii = pair<int,pi> ;
  8. void fill_ar(){
  9.     for(int i=1;i<=n;i++){
  10.         for(int j=1;j<=m;j++){
  11.             ar[i][j]=0;
  12.         }
  13.     }
  14. }
  15. bool check_ar(){
  16.     for(int i=1;i<=n;i++){
  17.         for(int j=1;j<=m;j++){
  18.             if(ar[i][j]==0) return false;
  19.         }
  20.     }
  21.     return true;
  22. }
  23. bool position(int i,int j){
  24.     return i>=1 and i<=n and j>=1 and j<=m and ar[i][j]==0;
  25. }
  26. void bfs(int x){
  27.     queue <pii> q;
  28.     q.push({x,{1,1}});
  29.  
  30.     while(q.size()>0){
  31.  
  32.         int ui,uj;
  33.         x=q.front().first;
  34.         ui=q.front().second.first;
  35.         uj=q.front().second.second;
  36.         ar[ui][uj]=x;
  37.         q.pop();
  38.  
  39.         if(l[x]!=0 and position(ui,uj-1)) q.push({l[x],{ui,uj-1}});
  40.         if(r[x]!=0 and position(ui,uj+1)) q.push({r[x],{ui,uj+1} });
  41.         if(up[x]!=0 and position(ui-1,uj)) q.push({up[x],{ui-1,uj}});
  42.         if(down[x]!=0 and position(ui+1,uj)) q.push({down[x],{ui+1,uj}});
  43.     }
  44. }
  45. int main(){
  46.  
  47.     scanf("%d%d",&n,&m);
  48.     for(int i=1;i<=n*m-1;i++){
  49.         int a,b;
  50.         char opr;
  51.         scanf("%d %c %d",&a,&opr,&b);
  52.         a++;
  53.         b++;
  54.         if(opr=='U'){
  55.             up[b]=a;
  56.             down[a]=b;
  57.         }
  58.         else if(opr=='L'){
  59.             l[b]=a;
  60.             r[a]=b;
  61.         }
  62.     }
  63.  
  64.  
  65.     for(int i=1;i<=n*m;i++){
  66.         if(up[i]==0 and l[i]==0) {
  67.             bfs(i);
  68.             if(check_ar()) break;
  69.             else fill_ar();
  70.         }
  71.     }
  72.  
  73.     for(int i=1;i<=n;i++){
  74.         for(int j=1;j<=m;j++){
  75.             printf("%d ",ar[i][j]-1);
  76.         }
  77.         printf("\n");
  78.     }
  79.  
  80.  
  81.     return 0;
  82. }
  83. /*
  84.  
  85. 3 3
  86. 1 U 2
  87. 5 L 1
  88. 0 L 4
  89. 8 L 5
  90. 4 L 7
  91. 3 L 6
  92. 8 U 3
  93. 2 U 7
  94.  
  95. 8 5 1
  96. 3 6 2
  97. 0 4 7
  98.  
  99. */
Advertisement
RAW Paste Data Copied
Advertisement