fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. #include <queue>
  4. #include <cmath>
  5. using namespace std;
  6.  
  7. #define FOR(i,a,b) for(short i=a; i<=b; ++i)
  8. #define endl '\n'
  9. #define x    first
  10. #define y    second
  11. const short max_n = 500;
  12.  
  13. short n;
  14. long MAX = 0;
  15. long a[max_n+2][max_n+2];
  16. bool check[max_n+1][max_n+1];
  17.  
  18. void debug(long high, long cnt)
  19. {
  20.     cerr << endl;
  21.     cerr << "high: " << high << endl;
  22.     cerr << "cnt: " << cnt << endl;
  23.     FOR(i,1,n)
  24.     {
  25.         FOR(j,1,n) cerr << check[i][j] << ' ';
  26.         cerr << endl;
  27.     }
  28.     system("pause");
  29. }
  30.  
  31. void inp()
  32. {
  33.   //  freopen("ROBOT.INP", "r", stdin);
  34.   //  freopen("ROBOT.OUT", "w", stdout);
  35.  
  36.     cin >> n;
  37.     FOR(i,1,n)
  38.         FOR(j,1,n)
  39.         {
  40.             cin >> a[i][j];
  41.             MAX = max(MAX, a[i][j]);
  42.         }
  43.  
  44.     FOR(i,1,n)
  45.     {
  46.         a[0][i] = -1;
  47.         a[n+1][i] = -1;
  48.         a[i][0] = -1;
  49.         a[i][n+1] = -1;
  50.     }
  51. }
  52.  
  53. long BFS(short x, short y, long high)
  54. {
  55.     queue< pair<long, long> > q;
  56.     short Ox[4] = {0, 0, -1, 1};
  57.     short Oy[4] = {1, -1, 0, 0};
  58.  
  59.     q.push({x,y});
  60.     long cnt = 1;
  61.     check[x][y] = true;
  62.     while (!q.empty())
  63.     {
  64.         pair <short, short> top;
  65.         top = q.front(); q.pop();
  66.  
  67.         FOR(i,0,3)
  68.         {
  69.             short xx = top.x + Oy[i];
  70.             short yy = top.y + Ox[i];
  71.  
  72.             if (a[xx][yy]!=-1 && !check[xx][yy] && abs(a[xx][yy] - a[x][y]) <= high)
  73.             {
  74.                 ++cnt;
  75.                 q.push({xx,yy});
  76.                 check[xx][yy] = true;
  77.             }
  78.         }
  79.     }
  80.    // debug(high, cnt);
  81.     return cnt;
  82. }
  83.  
  84. bool check_high(long high)
  85. {
  86.     memset(check, false, sizeof(check));
  87.     FOR(i, 1, n)
  88.         FOR(j, 1, n)
  89.             if (!check[i][j])
  90.                 if (BFS(i,j, high) >= floor(n*n/2.0d)) return true;
  91.     return false;
  92. }
  93.  
  94. int main()
  95. {
  96.     ios_base::sync_with_stdio(0);
  97.     cin.tie(0);
  98.  
  99.     inp();
  100.  
  101.     long l = 0, r = MAX, res = 0;
  102.     while (l<=r)
  103.     {
  104.         long mid = (l+r) / 2;
  105.         if (check_high(mid))
  106.         {
  107.             res = mid;
  108.             r = mid - 1;
  109.         } else l = mid + 1;
  110.     }
  111.  
  112.     cout << res;
  113.  
  114.     return 0;
  115. }
  116.  
Success #stdin #stdout 0s 5528KB
comments (?)
stdin
copy 
5
0 0 0 3 3
0 0 0 0 3
0 9 9 3 3
9 9 9 3 3
9 9 9 9 3
stdout
copy 
3
https://ideone.com/vcEvOG
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

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!