fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5.  
  6. const int N = 1e3 + 5;
  7. int n,m;
  8. int a[N][N] , b[N][N] , d[N][N];
  9. pair < int , int > s;
  10.  
  11. int dx[] = {0,1,0,-1},
  12.     dy[] = {1,0,-1,0};
  13.  
  14. bool BFS(int x){
  15.     memset(d,-1,sizeof(d));
  16.  
  17.     queue<pair<int,int>> Q;
  18.     d[s.first][s.second] = 0;
  19.     Q.push(s);
  20.     while(!Q.empty()){
  21.         int i = Q.front().first,
  22.             j = Q.front().second;
  23.         Q.pop();
  24.         for(int k=0; k<=3 ; k++){
  25.             int u = i + dx[k],
  26.                 v = j + dy[k];
  27.             if(d[u][v] != -1 || u<1 || v<1 || u>n || v>m ||
  28.             abs(a[i][j] - a[u][v]) > x) continue;
  29.             d[u][v] = d[i][j] + 1;
  30.             Q.push({u,v});
  31.         }
  32.     }
  33.     for(int i = 1 ; i <= n ; i++)
  34.         for(int j = 1 ; j <= m ; j++)
  35.             if(b[i][j] == 1 && d[i][j] == -1)
  36.                 return false;
  37.  
  38.     return true;
  39. }
  40.  
  41.  
  42.  
  43. main(){
  44.     ios_base::sync_with_stdio(0);
  45.     cin.tie(0);
  46.     cout.tie(0);
  47.  
  48.     cin >> n >> m;
  49.     for(int i = 1 ; i <= n ; i++)
  50.         for(int j = 1 ; j <= m ; j++)
  51.             cin >> a[i][j];
  52.  
  53.     for(int i = 1 ; i <= n ; i++)
  54.         for(int j = 1 ; j <= m ; j++)
  55.         {
  56.             cin >> b[i][j];
  57.             if(b[i][j] == 1)
  58.                 s = {i , j};
  59.         }
  60.  
  61.     int l = 0 , r = 1e9 , ans = -1;
  62.     /// log2(1e9) * (n * m)
  63.     while(l <= r)
  64.     {
  65.         int mid = (l + r) / 2;
  66.         if(BFS(mid) == true)
  67.         {
  68.             r = mid - 1;
  69.             ans = mid;
  70.         }
  71.         else
  72.             l = mid + 1;
  73.     }
  74.     cout << ans;
  75. }
  76.  
  77.  
Success #stdin #stdout 0.02s 13376KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/JVc8Q0
language:
C++14 (gcc 8.3)
created:
8 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!