Advertisement
erek1e

IOI '94 P2 - The Castle

Jun 5th, 2022
925
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.81 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. vector<vector<int>> g, component;
  8. vector<int> cSize;
  9. pair<int, int> direction[4] {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
  10.  
  11. int dfs(int i, int j, int c) {
  12.     component[i][j] = c;
  13.     int cnt = 1;
  14.     for (int dir = 0; dir < 4; ++dir) {
  15.         int ii = i+direction[dir].first, jj = j+direction[dir].second;
  16.         if (!(g[i][j] & (1 << dir)) && component[ii][jj] == -1) { // no wall in this direction
  17.             cnt += dfs(ii, jj, c);
  18.         }
  19.     }
  20.     return cnt;
  21. }
  22.  
  23. int main() {
  24.     int m, n;
  25.     cin >> m >> n;
  26.     g.resize(n), component.resize(n);
  27.     for (int i = 0; i < n; ++i) {
  28.         g[i].resize(m);
  29.         component[i] = vector<int>(m, -1);
  30.         for (int j = 0; j < m; ++j) cin >> g[i][j];
  31.     }
  32.     for (int i = 0; i < n; ++i) {
  33.         for (int j = 0; j < m; ++j) {
  34.             if (component[i][j] == -1) cSize.push_back(dfs(i, j, cSize.size()));
  35.         }
  36.     }
  37.     cout << cSize.size() << endl << *max_element(cSize.begin(), cSize.end()) << endl;
  38.  
  39.     int maxSize = 0; string maxWall = "";
  40.     for (int j = 0; j < m; ++j) {
  41.         for (int i = n-1; i >= 0; --i) {
  42.             for (int dir = 1; dir <= 2; ++dir) {
  43.                 int ii = i + direction[dir].first, jj = j + direction[dir].second;
  44.                 if (ii < 0 || jj >= m) continue;
  45.                 if (component[i][j] == component[ii][jj]) continue;
  46.                 int curSize = cSize[component[i][j]] + cSize[component[ii][jj]];
  47.                 if (curSize > maxSize) {
  48.                     maxSize = curSize;
  49.                     maxWall = to_string(i+1) + " " + to_string(j+1) + " " + string(1, 'N' + (dir-1)*('E'-'N'));
  50.                 }
  51.             }
  52.         }
  53.     }
  54.     cout << maxSize << endl << maxWall << endl;
  55.     return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement