fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define endl "\n"
  4. using namespace std;
  5.  
  6. const int N = 1e3 + 10;
  7. const ll INF = 1e18 + 7;
  8. vector<pair<ll,ll>> movements = {
  9.     {-1,0}, {1,0}, {0,-1}, {0,1},
  10.     {1,1}, {-1,1}, {1,-1}, {-1,-1}
  11. };
  12. ll a[N][N];
  13. ll level[N][N];
  14. ll visited[N][N];
  15. ll n, m; 
  16.  
  17. void reset() {
  18.     for(ll i = 0; i < N; i++) {
  19.         for(ll j = 0; j < N; j++) {
  20.             level[i][j] = INF;
  21.             visited[i][j] = 0;
  22.         }
  23.     }
  24. }
  25.  
  26. bool valid(ll i, ll j) {
  27.     return (i >= 0 && j >= 0 && i < n && j < m);
  28. }
  29.  
  30. ll bfs() {
  31.     queue<pair<ll,ll>> q;
  32.     ll mx = 0;
  33.     for(ll i = 0; i < n; i++) {
  34.         for(ll j = 0; j < m; j++) {
  35.             mx = max(mx, a[i][j]);
  36.         }
  37.     }
  38.     for(ll i = 0; i < n; i++) {
  39.         for(ll j = 0; j < m; j++) {
  40.             if(a[i][j] == mx) {
  41.                 q.push({i, j});
  42.                 level[i][j] = 0;
  43.                 visited[i][j] = 1;
  44.             }
  45.         }
  46.     }
  47.  
  48.     ll ans = 0;
  49.  
  50.     while(!q.empty()) {
  51.         pair<ll,ll> current = q.front();
  52.         q.pop();
  53.         ll current_x = current.first;
  54.         ll current_y = current.second;
  55.         for(auto child: movements) {
  56.             ll child_x = current.first + child.first;
  57.             ll child_y = current.second + child.second;
  58.             if(!valid(child_x, child_y)) continue;
  59.             if(visited[child_x][child_y]) continue;
  60.             q.push({child_x, child_y});
  61.             visited[child_x][child_y] = 1;
  62.             level[child_x][child_y] = level[current_x][current_y] + 1;
  63.             ans = max(ans, level[child_x][child_y]);
  64.         }
  65.     }
  66.  
  67.     return ans;
  68. }
  69.  
  70. int main() {
  71.     ios_base::sync_with_stdio(false);
  72.     cin.tie(0);
  73.     ll t; cin >> t;
  74.     while(t--) {
  75.         reset();
  76.         cin >> n >> m;
  77.         for(ll i = 0; i < n; i++) {
  78.             for(ll j = 0; j < m; j++) {
  79.                 cin >> a[i][j];
  80.             }
  81.         }
  82.         cout << bfs() << endl;
  83.     }
  84. }
Success #stdin #stdout 0.01s 20996KB
comments (?)
stdin
copy 
3
2 2
1 1
1 1
2 2
1 1
1 2
3 4
1 2 1 2
1 1 1 2
1 1 2 2
stdout
copy 
0
1
2
https://ideone.com/q2dUak
language:
C++14 (gcc 8.3)
created:
13 hours 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!