Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <algorithm>
- using namespace std;
- const int N = 1001;
- const int INF = 1e9 + 1;
- const int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
- const int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};
- int n, m, dist[N][N];
- char a[N][N];
- int main()
- {
- cin >> n >> m;
- for (int i = 0; i < n; i++)
- for (int j = 0; j < m; j++) {
- cin >> a[i][j];
- dist[i][j] = INF;
- }
- queue<pair<int, int>> q;
- int k;
- cin >> k;
- for (int i = 0; i < k; i++) {
- int x, y;
- cin >> x >> y;
- x--;
- y--;
- dist[x][y] = 0;
- q.push({x, y});
- }
- while (!q.empty()) {
- auto [x, y] = q.front();
- q.pop();
- ///check neighbours
- for (int d = 0; d < 8; d++) {
- int ax = x + dx[d];
- int ay = y + dy[d];
- if (ax >= 0 && ax < n && ay >= 0 && ay < m && a[ax][ay] == '.' && dist[ax][ay] == INF) {
- dist[ax][ay] = dist[x][y] + 1;
- q.push({ax, ay});
- }
- }
- }
- int mx = -1;
- for (int i = 0; i < n; i++)
- for (int j = 0; j < m; j++)
- if (dist[i][j] != INF)
- mx = max(mx, dist[i][j]);
- vector<pair<int, int>> ans;
- for (int i = 0; i < n; i++)
- for (int j = 0; j < m; j++)
- if (dist[i][j] == mx)
- ans.push_back({i, j});
- cout << ans.size() << "\n";
- for (auto [x, y] : ans)
- cout << x + 1 << ' ' << y + 1 << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement