fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int dx[] = {-1,0,0,1}, dy[] = {0,-1,1,0};
  5.  
  6. bool check(vector<vector<int>>& dist, int& r, int& C, int& k) {
  7.     pair<int,int> a = {INT_MIN,0}, b = {INT_MAX,0}, c = {0,INT_MIN}, d = {0,INT_MAX};
  8.     bool already_satisfied = true;
  9.     for (int i=0; i<r; i++) {
  10.         for (int j=0; j<C; j++) {
  11.             if (dist[i][j]>k) {
  12.                 already_satisfied = false;
  13.                 if (i+j>a.first)
  14.                     a = {i+j,i-j};
  15.                 if (i+j<b.first)
  16.                     b = {i+j,i-j};
  17.                 if (i-j>c.second)
  18.                     c = {i+j,i-j};
  19.                 if (i-j<d.second)
  20.                     d = {i+j,i-j};
  21.             }
  22.         }
  23.     }
  24.     if (already_satisfied) return true;
  25.     for (int i=0; i<r; i++) {
  26.         for (int j=0; j<C; j++) {
  27.             if (dist[i][j]>0) {
  28.                 int parm1 = max(abs(i+j-a.first),abs(i-j-a.second));
  29.                 int parm2 = max(abs(i+j-b.first),abs(i-j-c.second));
  30.                 int parm3 = max(abs(i+j-c.first),abs(i-j-b.second));
  31.                 int parm4 = max(abs(i+j-d.first),abs(i-j-d.second));
  32.                 if (max(max(parm1,parm2),max(parm3,parm4))<=k)
  33.                     return true;
  34.             }
  35.         }
  36.     }
  37.     return false;
  38. }
  39.  
  40. int solve() {
  41.     int r,c;
  42.     cin>>r>>c;
  43.     vector<vector<int>> dist(r,vector<int>(c,-1));
  44.     string s;
  45.     queue<pair<int,int>> _bfs;
  46.     for (int i=0; i<r; i++) {
  47.         cin>>s;
  48.         for (int j=0; j<c; j++) {
  49.             if (s[j]=='1') {
  50.                 dist[i][j] = 0;
  51.                 _bfs.push({i,j});
  52.             }
  53.         }
  54.     }
  55.     while (!_bfs.empty()) {
  56.         pair<int,int> p = _bfs.front();
  57.         _bfs.pop();
  58.         int x = p.first, y = p.second;
  59.         for (int k=0; k<4; k++) {
  60.             int _x = x + dx[k], _y = y + dy[k];
  61.             if (_x>=0 && _x<r && _y>=0 && _y<c && dist[_x][_y]<0) {
  62.                 dist[_x][_y] = 1 + dist[x][y];
  63.                 _bfs.push({_x,_y});
  64.             }
  65.         }
  66.     }
  67.     int lo = 0, hi = r+c-2, mi;
  68.     while (lo<hi) {
  69.         mi = (lo+hi)/2;
  70.         if (check(dist,r,c,mi))
  71.             hi = mi;
  72.         else lo = mi + 1;
  73.     }
  74.     return lo;
  75. }
  76. int main() {
  77.     ios_base::sync_with_stdio(false);
  78.     cin.tie(0);
  79.     cout.tie(0);
  80.  
  81.     int t;
  82.     cin>>t;
  83.     for (int i=1;i<=t;i++) {
  84.         cout<<"Case #"<<i<<": "<<solve()<<"\n";
  85.     }
  86. }
  87.  
Success #stdin #stdout 0s 4468KB
comments (?)
stdin
copy 
3
3 3
101
000
101
1 2
11
5 5
10001
00000
00000
00000
10001
stdout
copy 
Case #1: 1
Case #2: 0
Case #3: 2
https://ideone.com/ZwlSXt
language:
C++14 (gcc 8.3)
created:
4 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!