fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/bKn6UB
language:
C++ (gcc 8.3)
created:
192 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!