Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <utility>
- #include <climits>
- #include <queue>
- struct solve {
- int x;
- int y;
- int d;
- solve(int x1, int y1, int d1)
- : x(x1), y(y1), d(d1)
- {
- }
- };
- void bfs(int xi, int yi, int n, int m, int k, bool memo[102][102]) {
- int dx[] = { -1, -1, +0, +1, +1, +1, +0, -1 };
- int dy[] = { +0, -1, -1, -1, +0, +1, +1, +1 };
- solve init(xi, yi, 0);
- std::queue<solve> cola;
- cola.push(init);
- while (!cola.empty( )) {
- solve now = cola.front( );
- cola.pop( );
- if (memo[now.x][now.y]) {
- continue;
- }
- memo[now.x][now.y] = true;
- for (int i = 0; i < 8; ++i) {
- int x = now.x + dx[i];
- int y = now.y + dy[i];
- if (x >= 0 && x < n && y >= 0 && y < m && now.d + 1 <= k) {
- solve res(x, y, now.d + 1);
- cola.push(res);
- }
- }
- }
- }
- int main()
- {
- std::ios_base::sync_with_stdio(0);
- std::cin.tie(0);
- std::cout.tie(0);
- bool memo[102][102];
- std::fill(&memo[0][0], &memo[102][0], 0);
- int n, m, c;
- std::cin >> n >> m >> c;
- std::pair<int, int> lista[c];
- for (int i = 0; i < c; ++i) {
- int x, y;
- std::cin >> x >> y;
- lista[i] = { x, y };
- }
- int k;
- std::cin >> k;
- for (int i = 0; i < c; ++i) {
- int x = lista[i].first;
- int y = lista[i].second;
- bfs(x, y, n, m, k, memo);
- }
- int res_final = INT_MIN;
- bool memo2[102][192] = { };
- auto busqueda = [&](int x, int y) {
- int res = 0;
- memo2[x][y] = true, ++res;
- std::vector<std::pair<int, int>> v = { {x, y} };
- do {
- auto actual = v.back();
- v.pop_back();
- std::pair<int, int> vecinos[] = {
- {actual.first-1, actual.second},
- {actual.first+1, actual.second},
- {actual.first, actual.second-1},
- {actual.first, actual.second+1},
- {actual.first-1, actual.second-1},
- {actual.first-1, actual.second+1},
- {actual.first+1, actual.second-1},
- {actual.first+1, actual.second+1}
- };
- for(auto current : vecinos) {
- if(0 <= current.first && current.first < n && 0 <= current.second && current.second < m && memo[current.first][current.second] && !memo2[current.first][current.second]) {
- memo2[current.first][current.second] = true, ++res;
- v.push_back(current);
- }
- }
- }while(!v.empty());
- res_final = (res > res_final ? res : res_final);
- };
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < m; ++j) {
- if(memo[i][j]) {
- busqueda(i, j);
- }
- }
- }
- std::cout << res_final << std::endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement