Advertisement
mickypinata

USACO-T021: The Castle

Nov 29th, 2021
670
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: castle
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. #define r first
  11. #define c second
  12. typedef pair<int, int> pii;
  13. typedef tuple<pii, pii, char> tppc;
  14.  
  15. const int N = 50 + 5;
  16. const int NN = 2500 + 5;
  17. const pii dir[4] = {pii(0, -1), pii(-1, 0), pii(0, 1), pii(1, 0)}; // W N E S
  18.  
  19. vector<tppc> walls;
  20. int board[N][N], cVertex[N][N], dens[NN], row, col;
  21. bool visited[N][N];
  22.  
  23. bool isInBoard(int r, int c){
  24.     return r >= 1 && r <= row && c >= 1 && c <= col;
  25. }
  26.  
  27. void BFS(pii st, int i){
  28.     queue<pii> que;
  29.     visited[st.r][st.c] = true;
  30.     cVertex[st.r][st.c] = i;
  31.     que.push(st);
  32.     while(!que.empty()){
  33.         int ur = que.front().r;
  34.         int uc = que.front().c;
  35.         que.pop();
  36.         ++dens[i];
  37.         for(int d = 0; d < 4; ++d){
  38.             int vr = ur + dir[d].r;
  39.             int vc = uc + dir[d].c;
  40.             if((board[ur][uc] & (1 << d)) == 0 && !visited[vr][vc]){
  41.                 visited[vr][vc] = true;
  42.                 cVertex[vr][vc] = i;
  43.                 que.emplace(vr, vc);
  44.             }
  45.         }
  46.     }
  47. }
  48.  
  49. int main(){
  50.     freopen("castle.in", "r", stdin);
  51.     freopen("castle.out", "w", stdout);
  52.  
  53.     scanf("%d%d", &col, &row);
  54.     for(int i = 1; i <= row; ++i){
  55.         for(int j = 1; j <= col; ++j){
  56.             scanf("%d", &board[i][j]);
  57.             if((board[i][j] & (1 << 1)) != 0 && isInBoard(i - 1, j)){ // N
  58.                 walls.emplace_back(pii(i, j), pii(i - 1, j), 'N');
  59.             }
  60.             if((board[i][j] & (1 << 2)) != 0 && isInBoard(i, j + 1)){ // E
  61.                 walls.emplace_back(pii(i, j), pii(i, j + 1), 'E');
  62.             }
  63.         }
  64.     }
  65.     int roomCnt = 0;
  66.     int mxDens = 0;
  67.     for(int i = 1; i <= row; ++i){
  68.         for(int j = 1; j <= col; ++j){
  69.             if(!visited[i][j]){
  70.                 BFS(pii(i, j), ++roomCnt);
  71.                 mxDens = max(mxDens, dens[roomCnt]);
  72.             }
  73.         }
  74.     }
  75.     cout << roomCnt << '\n' << mxDens << '\n';
  76.     int mx = 0;
  77.     pii ans;
  78.     char di;
  79.     for(tppc e : walls){
  80.         pii u = get<0>(e);
  81.         pii v = get<1>(e);
  82.         char d = get<2>(e);
  83.         if(cVertex[u.r][u.c] == cVertex[v.r][v.c]){
  84.             continue;
  85.         }
  86.         int sz = dens[cVertex[u.r][u.c]] + dens[cVertex[v.r][v.c]];
  87.         if(sz > mx){
  88.             mx = sz;
  89.             ans = u;
  90.             di = d;
  91.         } else if(sz == mx){
  92.             if(u.c < ans.c){
  93.                 ans = u;
  94.                 di = d;
  95.             } else if(u.c == ans.c){
  96.                 if(u.r > ans.r){
  97.                     ans = u;
  98.                     di = d;
  99.                 } else if(u.r == ans.r){
  100.                     if(d == 'N' && di == 'E'){
  101.                         di = d;
  102.                     }
  103.                 }
  104.             }
  105.         }
  106.     }
  107.     cout << mx << '\n' << ans.r << ' ' << ans.c << ' ' << di << '\n';
  108.  
  109.     fclose(stdin);
  110.     fclose(stdout);
  111.     return 0;
  112. }
  113.  
Advertisement
RAW Paste Data Copied
Advertisement