Advertisement
AlejandroGY

Untitled

Dec 17th, 2017
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.73 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <utility>
  5. #include <climits>
  6. #include <queue>
  7.  
  8. struct solve {
  9.     int x;
  10.     int y;
  11.     int d;
  12.     solve(int x1, int y1, int d1)
  13.     : x(x1), y(y1), d(d1)
  14.     {
  15.     }
  16. };
  17.  
  18. void bfs(int xi, int yi, int n, int m, int k, bool memo[102][102]) {
  19.     int dx[] = { -1, -1, +0, +1, +1, +1, +0, -1 };
  20.     int dy[] = { +0, -1, -1, -1, +0, +1, +1, +1 };
  21.  
  22.     solve init(xi, yi, 0);
  23.     std::queue<solve> cola;
  24.     cola.push(init);
  25.  
  26.     while (!cola.empty( )) {
  27.         solve now = cola.front( );
  28.         cola.pop( );
  29.  
  30.         if (memo[now.x][now.y]) {
  31.             continue;
  32.         }
  33.         memo[now.x][now.y] = true;
  34.  
  35.         for (int i = 0; i < 8; ++i) {
  36.             int x = now.x + dx[i];
  37.             int y = now.y + dy[i];
  38.  
  39.             if (x >= 0 && x < n && y >= 0 && y < m && now.d + 1 <= k) {
  40.                 solve res(x, y, now.d + 1);
  41.                 cola.push(res);
  42.             }
  43.         }
  44.     }
  45. }
  46.  
  47. int main()
  48. {
  49.     std::ios_base::sync_with_stdio(0);
  50.     std::cin.tie(0);
  51.     std::cout.tie(0);
  52.  
  53.     bool memo[102][102];
  54.     std::fill(&memo[0][0], &memo[102][0], 0);
  55.  
  56.     int n, m, c;
  57.     std::cin >> n >> m >> c;
  58.  
  59.     std::pair<int, int> lista[c];
  60.     for (int i = 0; i < c; ++i) {
  61.         int x, y;
  62.         std::cin >> x >> y;
  63.         lista[i] = { x, y };
  64.     }
  65.  
  66.     int k;
  67.     std::cin >> k;
  68.  
  69.     for (int i = 0; i < c; ++i) {
  70.         int x = lista[i].first;
  71.         int y = lista[i].second;
  72.  
  73.         bfs(x, y, n, m, k, memo);
  74.     }
  75.  
  76.     int res_final = INT_MIN;
  77.     bool memo2[102][192] = { };
  78.  
  79.     auto busqueda = [&](int x, int y) {
  80.         int res = 0;
  81.         memo2[x][y] = true, ++res;
  82.         std::vector<std::pair<int, int>> v = { {x, y} };
  83.         do {
  84.             auto actual = v.back();
  85.             v.pop_back();
  86.             std::pair<int, int> vecinos[] = {
  87.                 {actual.first-1, actual.second},
  88.                 {actual.first+1, actual.second},
  89.                 {actual.first, actual.second-1},
  90.                 {actual.first, actual.second+1},
  91.                 {actual.first-1, actual.second-1},
  92.                 {actual.first-1, actual.second+1},
  93.                 {actual.first+1, actual.second-1},
  94.                 {actual.first+1, actual.second+1}
  95.             };
  96.             for(auto current : vecinos) {
  97.                 if(0 <= current.first && current.first < n && 0 <= current.second && current.second < m && memo[current.first][current.second] && !memo2[current.first][current.second]) {
  98.                     memo2[current.first][current.second] = true, ++res;
  99.                     v.push_back(current);
  100.                 }
  101.             }
  102.         }while(!v.empty());
  103.         res_final = (res > res_final ? res : res_final);
  104.     };
  105.  
  106.     for (int i = 0; i < n; ++i) {
  107.         for (int j = 0; j < m; ++j) {
  108.             if(memo[i][j]) {
  109.                 busqueda(i, j);
  110.             }
  111.         }
  112.     }
  113.  
  114.     std::cout << res_final << std::endl;
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement