fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pii array<int,2>
  5.  
  6. pii operator+(const pii &x, const pii &y) {
  7. return {x[0]+y[0], x[1]+y[1]};
  8. }
  9.  
  10. const int GRID = 1000;
  11.  
  12. // counts the number of times a square is visited
  13. int cnt[GRID][GRID];
  14.  
  15. bool inside[GRID][GRID];
  16. vector<vector<int>> dist(GRID, vector<int>(GRID, 1e9));
  17.  
  18. int main() {
  19. ios::sync_with_stdio(false);
  20. cin.tie(0);
  21.  
  22. int n;cin>>n;
  23.  
  24. pii p;
  25.  
  26. for (int i=0;i<n;i++) {
  27. int x,y;cin>>x>>y;
  28. inside[x][y] = true;
  29. p = {x, y};
  30. }
  31.  
  32. priority_queue<pair<int, pii>> pq;
  33. pq.push(make_pair(0, p));
  34. dist[p[0]][p[1]] = 0;
  35. int ans = 0;
  36.  
  37. auto check=[&](pii x) {
  38. return x[0] >= 0 && x[0] < GRID && x[1] >= 0 && x[1] < GRID;
  39. };
  40.  
  41. vector<pii> dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
  42. vector<vector<int>> cnt(GRID, vector<int>(GRID, 0));
  43.  
  44.  
  45. while (!pq.empty()) {
  46. auto [d, e] = pq.top();
  47. int a = e[0];
  48. int b = e[1];
  49. pq.pop();
  50.  
  51. if (dist[a][b] != -d) continue;
  52.  
  53. if (inside[a][b]) {
  54. dist[a][b] = 0;
  55. }
  56.  
  57. cnt[a][b]++;
  58.  
  59. for (auto &x:dir) {
  60. pii nw = x+e;
  61. if (!check(nw)) continue;
  62. if (dist[nw[0]][nw[1]] > dist[a][b]+1) {
  63. dist[nw[0]][nw[1]] = dist[a][b]+1;
  64. pq.push({-(dist[a][b]+1), nw});
  65. }
  66. }
  67. }
  68.  
  69. // find the maximum number of visits
  70. int mx = 0;
  71.  
  72. for (int i=0;i<GRID;i++) {
  73. for (int j=0;j<GRID;j++) {
  74. mx = max(mx, cnt[i][j]);
  75. }
  76. }
  77.  
  78. cout<<mx<<"\n";
  79. }
Success #stdin #stdout 0.01s 11016KB
stdin
Standard input is empty
stdout
1