Advertisement
osipyonok

mx

May 6th, 2017
232
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.19 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. #define INF 1000010000
  4. #define nl '\n'
  5. #define pb push_back
  6. #define ppb pop_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define pii pair<int,int>
  11. #define pdd pair<double,double>
  12. #define all(c) (c).begin(), (c).end()
  13. #define SORT(c) sort(all(c))
  14. #define sz(c) (c).size()
  15. #define rep(i,n) for( int i = 0; i < n; ++i )
  16. #define repi(i,n) for( int i = 1 ; i <= n; ++i )
  17. #define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
  18. #define repf(j,i,n) for( int j = i ; j < n ; ++j )
  19. #define die(s) {std::cout << s << nl;}
  20. #define dier(s) {std::cout << s; return 0;}
  21. #define vi vector<int>
  22. typedef long long ll;
  23. #define MAXN 55
  24. using namespace std;
  25.  
  26. int n , m , k;
  27. vector<pii> life , magic;
  28.  
  29. vi dx = {1 , -1 , 0 , 0};
  30. vi dy = {0 , 0 , 1 , -1};
  31.  
  32. map<char , int> s;
  33.  
  34.  
  35. inline bool ok(pii p){
  36.     int x = p.fi;
  37.     int y = p.se;
  38.     return x >= 0 && x < n && y >= 0 && y < m;
  39. }
  40.  
  41. inline void fill(vector<vi> & v , pii a , pii b , char c){
  42.     for(int i = min(a.fi , b.fi) ; i <= max(a.fi , b.fi) ; ++i){
  43.         for(int j = min(a.se , b.se) ; j <= max(a.se , b.se) ; ++j){
  44.             if(v[i][j] < 3 ){
  45.                 v[i][j] = c;
  46.                 ++s[c];
  47.             }
  48.         }
  49.     }
  50. }
  51.  
  52. inline void fill2(vector<vi> & v , map<pii , pii> & pr , pii a , pii b , char c){
  53.     v[b.fi][b.se] = c;
  54.     while(b != a){
  55.         b = pr[b];
  56.         v[b.fi][b.se] = c;
  57.         ++s[c];
  58.     }
  59.     v[b.fi][b.se] = c;
  60. }
  61.  
  62. vector<vi> solve(const vector<pii> & life , const vector<pii> & magic){
  63.     s.clear();
  64.     vector<vi> v(MAXN , vi(MAXN , 0));
  65.    
  66.     queue<pii> q;
  67.    
  68.     rep(i , k){
  69.         v[life[i].fi][life[i].se] = 1;
  70.         v[magic[i].fi][magic[i].se] = 2;
  71.     }
  72.    
  73.     vi index(k);
  74.     rep(i , k){
  75.         queue<pii> q;
  76.         q.push({life[i]});
  77.        
  78.         index[i] = 'a' + i;
  79.        
  80.         v[life[i].fi][life[i].se] = 'a' + i;
  81.        
  82.         vector<vi> used(MAXN , vi(MAXN , 0));
  83.         map<pii , pii> pr;
  84.        
  85.         used[life[i].fi][life[i].se] = 1;
  86.         pr[life[i]] = {-1 , -1};
  87.        
  88.         while(sz(q)){
  89.             pii cur = q.front();
  90.             q.pop();
  91.             if(v[cur.fi][cur.se] > 2 && v[cur.fi][cur.se] != 'a' + i){
  92.                 continue;
  93.             }
  94.    
  95.             bool done = 0;
  96.             rep(j , 4){
  97.                 pii nxt = {cur.fi + dx[j] , cur.se + dy[j]};
  98.                 if(ok(nxt) && v[nxt.fi][nxt.se] < 3 && !used[nxt.fi][nxt.se]){
  99.                     if(v[nxt.fi][nxt.se] == 2){
  100.                         pr[nxt] = cur;
  101.                     //  fill(v , life[i] , nxt , 'a' + i);
  102.                         fill2(v , pr , life[i] , nxt , 'a' + i);
  103.                         done = 1;
  104.                         break;
  105.                     }else if(v[nxt.fi][nxt.se] == 0){
  106.                         pr[nxt] = cur;
  107.                         used[nxt.fi][nxt.se] = 1;
  108.                         q.push(nxt);
  109.                     }
  110.                 }
  111.             }
  112.             if(done){
  113.                 break;
  114.             }
  115.            
  116.         }
  117.        
  118.        
  119.     }
  120.     return v;
  121. }
  122.  
  123. void finalize(vector<vi> & v){
  124.     bool rec = 0;
  125.     rep(i , n){
  126.         rep(j , m){
  127.             if(v[i][j] == 0){
  128.                 vector<pii> ck;
  129.                 rep(l , 4){
  130.                     pii cur = {i + dx[l] , j + dy[l]};
  131.                     if(ok(cur) && v[cur.fi][cur.se] != 0){
  132.                         ck.pb({s[v[cur.fi][cur.se]] , v[cur.fi][cur.se]});
  133.                     }
  134.                 }
  135.                 SORT(ck);
  136.                 if(!sz(ck)){
  137.                     rec = 1;
  138.                     continue;
  139.                 }
  140.                 v[i][j] = ck[0].se;
  141.                 ++s[ck[0].se];
  142.             }
  143.         }
  144.     }
  145.     if(rec){
  146.         finalize(v);
  147.     }
  148. }
  149.  
  150. bool checker(vector<vi> & v , const vector<pii> & life , const vector<pii> & magic){
  151.     vector<vi> t(MAXN , vi(MAXN , 0));
  152.     rep(i , k){
  153.         t[life[i].fi][life[i].se] = 1;
  154.         t[magic[i].fi][magic[i].se] = 2;       
  155.     }
  156.     rep(l , k){
  157.         int cur = 'a' + l;
  158.         int source = 0;
  159.         int target = 0;
  160.         pii so , ta;
  161.         int cnt = 0;
  162.         rep(i , n){
  163.             rep(j , m){
  164.                 if(v[i][j] == cur){
  165.                     ++cnt;
  166.                     if(t[i][j] == 2){
  167.                         if(!target){
  168.                             ++target;
  169.                             ta = {i , j};
  170.                         }else{
  171.                             return 0;
  172.                         }
  173.                     }
  174.                     if(t[i][j] == 1){
  175.                         if(!source){
  176.                             ++source;
  177.                             so = {i , j};
  178.                         }else{
  179.                             return 0;
  180.                         }
  181.                     }
  182.                 }
  183.             }
  184.         }
  185.         if(target != 1 || source != 1)return 0;
  186.        
  187.         vector<vi> used(MAXN , vi(MAXN , 0));
  188.        
  189.         used[so.fi][so.se] = 1;
  190.         queue<pii> q;
  191.         q.push(so);
  192.        
  193.         while(sz(q)){
  194.             pii c = q.front();
  195.             q.pop();
  196.             if(v[c.fi][c.se] == cur){
  197.                 --cnt;
  198.             }
  199.             rep(i , 4){
  200.                 pii nxt = {c.fi + dx[i] , c.se + dy[i]};
  201.                 if(ok(nxt) && !used[nxt.fi][nxt.se] && v[nxt.fi][nxt.se] == cur){
  202.                     used[nxt.fi][nxt.se] = 1;
  203.                     q.push(nxt);
  204.                 }
  205.             }
  206.         }
  207.         if(cnt)return 0;
  208.     }
  209.     return 1;
  210. }
  211.  
  212. int main() {
  213.     ios_base::sync_with_stdio(false);
  214.     cin.tie(NULL);
  215.     cout.precision(0);
  216.  
  217.     cin >> n >> m >> k;
  218.     life.resize(k);
  219.     magic.resize(k);
  220.    
  221.     rep(i , k){
  222.         cin >> life[i].fi >> life[i].se;
  223.     }
  224.    
  225.     rep(i , k){
  226.         cin >> magic[i].fi >> magic[i].se;
  227.     }
  228.    
  229.     struct{
  230.         bool operator()(pii & a , pii & b){  
  231.             int d1 = INF , d2 = INF;
  232.             rep(i , k){
  233.                 d1 =  min(d1 , abs(a.fi - magic[i].fi) + abs(a.se - magic[i].se));
  234.                 d2 =  min(d2 , abs(b.fi - magic[i].fi) + abs(b.se - magic[i].se));
  235.             }
  236.             return d1 < d2;
  237.         }  
  238.     }comp;
  239.  
  240.     sort(all(life) , comp);
  241.  
  242.     auto v1 = solve(life , magic);
  243.    
  244.     finalize(v1);
  245.    
  246. //  auto v2 = solve(magic , life);
  247.     ll start = clock();
  248.    
  249.     if(checker(v1 , life , magic) == 0){
  250.         do{
  251.             random_shuffle(all(life));
  252.             random_shuffle(all(magic));
  253.             v1 = solve(life , magic);
  254.             finalize(v1);
  255.         //  if(clock() - start > 1950)break;
  256.         }while(checker(v1 , life , magic) == 0);
  257.     }
  258.    
  259.     rep(i , n){
  260.         rep(j , m){
  261.             cout << (char)v1[i][j];
  262.         }
  263.         cout << nl;
  264.     }  
  265.     return 0;
  266. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement