fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5.         int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};
  6.         int tt;cin>>tt;
  7.         for(int t=1;t<=tt;t++){
  8.                 int r,c;cin>>r>>c;
  9.                 vector<string> initial;
  10.                 for(int i=0;i<r;i++){
  11.                         string row;cin>>row;
  12.                         initial.push_back(row);
  13.                 }
  14.                 vector<vector<int> > dist;
  15.                 queue<pair<int,int> > q;
  16.                 for(int i=0;i<r;i++){
  17.                         vector<int> row;
  18.                         for(int j=0;j<c;j++){
  19.                                 if(initial[i][j]=='1'){
  20.                                         row.push_back(0);
  21.                                         q.push(make_pair(i,j));
  22.                                 }else row.push_back(INT_MAX);
  23.                         }
  24.                         dist.push_back(row);
  25.                 }
  26.                 int max_dist=0;
  27.                 while(!q.empty()){
  28.                         int x = q.front().first,y = q.front().second;
  29.                         q.pop();
  30.                         max_dist = max(max_dist,dist[x][y]);
  31.                         for(int i=0;i<4;i++){
  32.                                 int xx = x+dx[i],yy = y+dy[i];
  33.                                 if(xx>=0 && xx<r && yy>=0 && yy<c){
  34.                                         if(dist[xx][yy]>dist[x][y]+1){
  35.                                                 dist[xx][yy] = dist[x][y]+1;
  36.                                                 q.push(make_pair(xx,yy));
  37.                                         }
  38.                                 }
  39.                         }
  40.                 }
  41.                 int lower=-1,upper=max_dist;
  42.                 while(upper-lower>1){
  43.                         int mid = (upper+lower)/2;
  44.                         int ipjmax=-r-c-1,ipjmin=r+c+1,imjmax=-r-c-1,imjmin=r+c+1;
  45.                         for(int i=0;i<r;i++){
  46.                                 for(int j=0;j<c;j++){
  47.                                         if(dist[i][j]>mid){
  48.                                                 ipjmin = min(i+j,ipjmin);
  49.                                                 ipjmax = max(i+j,ipjmax);
  50.                                                 imjmin = min(i-j,imjmin);
  51.                                                 imjmax = max(i-j,imjmax);
  52.                                         }
  53.                                 }
  54.                         }
  55.                         if(ipjmax-ipjmin<=2*mid && imjmax-imjmin<2*mid
  56.                         	|| ipjmax-ipjmin<2*mid && imjmax-imjmin<=2*mid
  57.                         	|| ipjmax-ipjmin==2*mid && imjmax-imjmin==2*mid && (ipjmax + imjmax) % 2 == 0) {
  58.                         	upper = mid;
  59.                         }
  60.                         else lower = mid;
  61.                 }
  62.                 cout<<"Case #"<<t<<": "<<upper<<endl;
  63.         }
  64.         return 0;
  65. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
1
4 4
1001
0000
0000
1001
stdout 
Case #1: 2
https://ideone.com/7xQxtR
language:
C++14 (gcc 8.3)
created:
6 years 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!