SHARE
TWEET

Untitled

a guest Aug 14th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <set>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8.  
  9. const int N = 107;
  10. const int K = N*N;
  11. const int D = 8;
  12.  
  13. int dx[D] = { +1, +1, -1, -1, +2, +2, -2, -2 };
  14. int dy[D] = { +2, -2, +2, -2, +1, -1, +1, -1 };
  15.  
  16. char s[N][N];
  17. int n, m;
  18. int st[N][N], fsz;
  19. int ps[N][N];
  20.  
  21. struct MST {
  22.     int p[8], pos, cnt;
  23.     int x, y;
  24.  
  25.     void clear() {
  26.  
  27.     }
  28. } mstack[K];
  29. int mstack_l;
  30.  
  31. #define MTOP mstack[mstack_l]
  32.  
  33. void ms_push(int qx, int qy) {
  34.     mstack_l++;
  35.     MTOP.cnt = 0;
  36.     MTOP.pos = 0;
  37.     MTOP.x = qx;
  38.     MTOP.y = qy;
  39. }
  40.  
  41. void ms_pop() {
  42.     mstack_l--;
  43. }
  44.  
  45. bool is_opened(int x, int y) {
  46.     if(x < 0 || y < 0 || x >= m || y >= n)
  47.         return false;
  48.     return s[y][x] != 'X' && st[x][y] == 0;
  49. }
  50.  
  51. void try_push(int qx, int qy) {
  52.     if(is_opened(qx, qy)) {
  53.         ms_push(qx, qy);
  54.         ps[qx][qy] = mstack_l;
  55.         st[qx][qy] = 1;
  56.     }
  57. }
  58.  
  59. int main() {
  60.     ios_base::sync_with_stdio(false); cin.tie(0);
  61.  
  62.     cin >> n >> m;
  63.     for(int i = 0; i < n; ++i) {
  64.         cin >> s[i];
  65.         for(int j = 0; j < m; ++j) {
  66.             if(s[i][j] == 'K') {
  67.                 s[i][j] = '.';
  68.                 try_push(j, i);
  69.             }
  70.  
  71.             if(s[i][j] == '.') fsz++;
  72.         }
  73.     }
  74.  
  75.     while(mstack_l != 0 && mstack_l != fsz) {
  76.         int cx = MTOP.x, cy = MTOP.y;
  77.         int* cp = MTOP.p;
  78.         int& ccnt = MTOP.cnt;
  79.         int& cpos = MTOP.pos;
  80.  
  81.         if(st[cx][cy] == 1) {
  82.             //cout << "[POINT : " << cx << " ; " << cy << "]" << endl;
  83.  
  84.             int cpc[8] = { 0 };
  85.  
  86.             for(int i = 0; i < 8; ++i) {
  87.                 if(!is_opened(cx+dx[i], cy+dy[i])) continue;
  88.                  
  89.                 cp[ccnt] = i;
  90.                 for(int j = 0; j < 8; ++j)
  91.                     if(is_opened(cx+dx[i]+dx[j], cy+dy[i]+dy[j]))
  92.                         ++cpc[i];
  93.  
  94.                 if(cpc[i] != 0 || mstack_l+1 == fsz) ccnt++;
  95.             }
  96.  
  97.             sort(cp, cp+ccnt, [&](int a, int b) {
  98.                 return cpc[a] < cpc[b];
  99.             });
  100.  
  101.             /*
  102.             for(int i = 0; i < ccnt; ++i) {
  103.                 cout << "  [WAY : " << cx+dx[cp[i]] << " ; " << cy+dy[cp[i]] << "] => " << cpc[cp[i]] << endl;
  104.             }
  105.             */
  106.  
  107.             st[cx][cy] = 2;
  108.         }
  109.  
  110.         if(st[cx][cy] == 2) {
  111.             if(cpos == ccnt) {
  112.                 st[cx][cy] = 0;
  113.                 ms_pop();
  114.                 continue;
  115.             }
  116.  
  117.             int nx = cx+dx[cp[cpos]];
  118.             int ny = cy+dy[cp[cpos]];
  119.  
  120.             try_push(nx, ny);
  121.  
  122.             cpos++;
  123.             continue;
  124.         }
  125.     }
  126.  
  127.     for(int i = 0; i < n; ++i) {
  128.         for(int j = 0; j < m; ++j) {
  129.             printf("%3d ", ps[j][i]);
  130.             // cout << ps[j][i] << ' ';
  131.         }
  132.         cout << endl;
  133.     }
  134. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top