fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. int dx[5] = {-1,0,1,0};
  5. int dy[5] = {0,1,0,-1};
  6. int r,c;
  7. const int MAXN = 300;
  8. int grid[MAXN][MAXN];
  9. int dp[MAXN][MAXN];
  10. bool check(int x,int y){
  11.     if(x<=0||y<=0||x>r||y>c||dp[x][y]!=-1){
  12.  
  13.         return false;
  14.     }
  15.     return true;
  16. }
  17. bool check2(int k){
  18.     int max1 = 0;
  19.     int min1 =r+c;
  20.     int max2 = 0;
  21.     int min2 = r+c;
  22.     bool ok = false;
  23.     for(int i=1;i<=r;i++){
  24.         for(int j=1;j<=c;j++){
  25.  
  26.             if(dp[i][j]<=k){
  27.                 continue;
  28.             }
  29.             ok = true;
  30.             max1 = max(max1,i+j);
  31.             min1 = min(min1,i+j);
  32.             max2 = max(max2,i-j);
  33.             min2 = min(min2,i-j);
  34.  
  35.  
  36.         }
  37.     }
  38.     if(!ok){
  39.         return true;
  40.     }
  41.     for(int i=1;i<=r;i++){
  42.         for(int j=1;j<=c;j++){
  43.             if(dp[i][j] == 0){
  44.                 continue;
  45.             }
  46.             int ok1 = abs(max1-(i+j));
  47.             int ok2 = abs(min1-(i+j));
  48.             int ok3 = abs(max2-(i-j));
  49.             int ok4 = abs(min2-(i-j));
  50.  
  51.             if(ok1<=k && ok2<=k && ok3<=k && ok4<=k){
  52.  
  53.  
  54.                 return true;
  55.             }
  56.         }
  57.     }
  58.  
  59.     return false;
  60. }
  61. void fix(){
  62.     for(int i=0;i<=r;i++){
  63.         for(int j=0;j<=c;j++){
  64.             dp[i][j] = -1;
  65.             grid[i][j] = 0;
  66.         }
  67.     }
  68.  
  69. }
  70. int main() {
  71.     int t;
  72.     cin>>t;
  73.     for(int h=1;h<=t;h++){
  74.  
  75.  
  76.         cin>>r>>c;
  77.          fix();
  78.         deque<pair<int,int>> q1;
  79.         for(int i=1;i<=r;i++){
  80.             for(int j=1;j<=c;j++){
  81.                 char x;
  82.                 cin>>x;
  83.                 if(x == '1'){
  84.                     grid[i][j] = 1;
  85.                     dp[i][j] = 0;
  86.                     q1.push_back(make_pair(i,j));
  87.                 }else{
  88.                     grid[i][j] = 0;
  89.                 }
  90.             }
  91.         }
  92.         while(!q1.empty()){
  93.             auto hold = q1.front();
  94.             q1.pop_front();
  95.             int currr = hold.first;
  96.             int currc = hold.second;
  97.             for(int i=0;i<4;i++){
  98.                 int nextr = currr+dx[i];
  99.                 int nextc = currc+dy[i];
  100.  
  101.                 if(check(nextr,nextc)){
  102.                     dp[nextr][nextc] = dp[currr][currc] +1;
  103.  
  104.                     q1.push_back(make_pair(nextr,nextc));
  105.                 }
  106.             }
  107.         }
  108.  
  109.         int l =0 ;
  110.         int r =500;
  111.         int ans = 0;
  112.         while(l<=r){
  113.             int mid = (l+r)/2;
  114.  
  115.             if(check2(mid)){
  116.                 ans = mid;
  117.                 r = mid-1;
  118.             }else{
  119.                 l = mid+1;
  120.             }
  121.         }
  122.         cout<<"Case #"<<h<<": "<<ans<<endl;
  123.     }
  124. }
Success #stdin #stdout 0s 15936KB
comments (?)
stdin
copy 
1
2 3 
010
000
stdout
copy 
Case #1: 1
https://ideone.com/cR0pXA
language:
C++14 (gcc 8.3)
created:
5 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!