Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define INF 1000010000
- #define nl '\n'
- #define pb push_back
- #define ppb pop_back
- #define mp make_pair
- #define fi first
- #define se second
- #define pii pair<int,int>
- #define pdd pair<double,double>
- #define all(c) (c).begin(), (c).end()
- #define SORT(c) sort(all(c))
- #define sz(c) (c).size()
- #define rep(i,n) for( int i = 0; i < n; ++i )
- #define repi(i,n) for( int i = 1 ; i <= n; ++i )
- #define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
- #define repf(j,i,n) for( int j = i ; j < n ; ++j )
- #define die(s) {std::cout << s << nl;}
- #define dier(s) {std::cout << s; return 0;}
- #define vi vector<int>
- typedef long long ll;
- #define MAXN 55
- using namespace std;
- int n , m , k;
- vector<pii> life , magic;
- vi dx = {1 , -1 , 0 , 0};
- vi dy = {0 , 0 , 1 , -1};
- map<char , int> s;
- inline bool ok(pii p){
- int x = p.fi;
- int y = p.se;
- return x >= 0 && x < n && y >= 0 && y < m;
- }
- inline void fill(vector<vi> & v , pii a , pii b , char c){
- for(int i = min(a.fi , b.fi) ; i <= max(a.fi , b.fi) ; ++i){
- for(int j = min(a.se , b.se) ; j <= max(a.se , b.se) ; ++j){
- if(v[i][j] < 3 ){
- v[i][j] = c;
- ++s[c];
- }
- }
- }
- }
- inline void fill2(vector<vi> & v , map<pii , pii> & pr , pii a , pii b , char c){
- v[b.fi][b.se] = c;
- while(b != a){
- b = pr[b];
- v[b.fi][b.se] = c;
- ++s[c];
- }
- v[b.fi][b.se] = c;
- }
- vector<vi> solve(const vector<pii> & life , const vector<pii> & magic){
- s.clear();
- vector<vi> v(MAXN , vi(MAXN , 0));
- queue<pii> q;
- rep(i , k){
- v[life[i].fi][life[i].se] = 1;
- v[magic[i].fi][magic[i].se] = 2;
- }
- vi index(k);
- rep(i , k){
- queue<pii> q;
- q.push({life[i]});
- index[i] = 'a' + i;
- v[life[i].fi][life[i].se] = 'a' + i;
- vector<vi> used(MAXN , vi(MAXN , 0));
- map<pii , pii> pr;
- used[life[i].fi][life[i].se] = 1;
- pr[life[i]] = {-1 , -1};
- while(sz(q)){
- pii cur = q.front();
- q.pop();
- if(v[cur.fi][cur.se] > 2 && v[cur.fi][cur.se] != 'a' + i){
- continue;
- }
- bool done = 0;
- rep(j , 4){
- pii nxt = {cur.fi + dx[j] , cur.se + dy[j]};
- if(ok(nxt) && v[nxt.fi][nxt.se] < 3 && !used[nxt.fi][nxt.se]){
- if(v[nxt.fi][nxt.se] == 2){
- pr[nxt] = cur;
- // fill(v , life[i] , nxt , 'a' + i);
- fill2(v , pr , life[i] , nxt , 'a' + i);
- done = 1;
- break;
- }else if(v[nxt.fi][nxt.se] == 0){
- pr[nxt] = cur;
- used[nxt.fi][nxt.se] = 1;
- q.push(nxt);
- }
- }
- }
- if(done){
- break;
- }
- }
- }
- return v;
- }
- void finalize(vector<vi> & v){
- bool rec = 0;
- rep(i , n){
- rep(j , m){
- if(v[i][j] == 0){
- vector<pii> ck;
- rep(l , 4){
- pii cur = {i + dx[l] , j + dy[l]};
- if(ok(cur) && v[cur.fi][cur.se] != 0){
- ck.pb({s[v[cur.fi][cur.se]] , v[cur.fi][cur.se]});
- }
- }
- SORT(ck);
- if(!sz(ck)){
- rec = 1;
- continue;
- }
- v[i][j] = ck[0].se;
- ++s[ck[0].se];
- }
- }
- }
- if(rec){
- finalize(v);
- }
- }
- bool checker(vector<vi> & v , const vector<pii> & life , const vector<pii> & magic){
- vector<vi> t(MAXN , vi(MAXN , 0));
- rep(i , k){
- t[life[i].fi][life[i].se] = 1;
- t[magic[i].fi][magic[i].se] = 2;
- }
- rep(l , k){
- int cur = 'a' + l;
- int source = 0;
- int target = 0;
- pii so , ta;
- int cnt = 0;
- rep(i , n){
- rep(j , m){
- if(v[i][j] == cur){
- ++cnt;
- if(t[i][j] == 2){
- if(!target){
- ++target;
- ta = {i , j};
- }else{
- return 0;
- }
- }
- if(t[i][j] == 1){
- if(!source){
- ++source;
- so = {i , j};
- }else{
- return 0;
- }
- }
- }
- }
- }
- if(target != 1 || source != 1)return 0;
- vector<vi> used(MAXN , vi(MAXN , 0));
- used[so.fi][so.se] = 1;
- queue<pii> q;
- q.push(so);
- while(sz(q)){
- pii c = q.front();
- q.pop();
- if(v[c.fi][c.se] == cur){
- --cnt;
- }
- rep(i , 4){
- pii nxt = {c.fi + dx[i] , c.se + dy[i]};
- if(ok(nxt) && !used[nxt.fi][nxt.se] && v[nxt.fi][nxt.se] == cur){
- used[nxt.fi][nxt.se] = 1;
- q.push(nxt);
- }
- }
- }
- if(cnt)return 0;
- }
- return 1;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.precision(0);
- cin >> n >> m >> k;
- life.resize(k);
- magic.resize(k);
- rep(i , k){
- cin >> life[i].fi >> life[i].se;
- }
- rep(i , k){
- cin >> magic[i].fi >> magic[i].se;
- }
- struct{
- bool operator()(pii & a , pii & b){
- int d1 = INF , d2 = INF;
- rep(i , k){
- d1 = min(d1 , abs(a.fi - magic[i].fi) + abs(a.se - magic[i].se));
- d2 = min(d2 , abs(b.fi - magic[i].fi) + abs(b.se - magic[i].se));
- }
- return d1 < d2;
- }
- }comp;
- sort(all(life) , comp);
- auto v1 = solve(life , magic);
- finalize(v1);
- // auto v2 = solve(magic , life);
- ll start = clock();
- if(checker(v1 , life , magic) == 0){
- do{
- random_shuffle(all(life));
- random_shuffle(all(magic));
- v1 = solve(life , magic);
- finalize(v1);
- // if(clock() - start > 1950)break;
- }while(checker(v1 , life , magic) == 0);
- }
- rep(i , n){
- rep(j , m){
- cout << (char)v1[i][j];
- }
- cout << nl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement