fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const ll MOD = 1e9+7;
  5. const int N = 505;
  6. const short dx[]={1,0,-1,0};
  7. const short dy[]={0,1,0,-1};
  8.  
  9. int n,m,xa,xb,ya,yb;
  10. int sum[N][N],cana[N][N];
  11. bool vis[N][N];
  12. string s[N];
  13.  
  14. bool ok(int x,int y){
  15.     if(x<1||y<1||x>n||y>n||s[x][y]=='X')return false;
  16.     return true;
  17. }
  18.  
  19. int getsum(int x1,int y1,int x2,int y2){
  20.     return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
  21. }
  22.  
  23. bool solve(int k){
  24.     if(m==1){
  25.         for(int i=1;i<=n;i++){
  26.             for(int j=1;j<=n;j++){
  27.                 if(!cana[i][j])continue;
  28.                 int ss=getsum(max(1,i-k-1),max(1,j-k-1),min(n,i+k+1),min(n,j+k+1));
  29.                 if(i-k-1>=1&&j-k-1>=1)ss-=getsum(i-k-1,j-k-1,i-k-1,j-k-1);
  30.                 if(i-k-1>=1&&j+k+1<=n)ss-=getsum(i-k-1,j+k+1,i-k-1,j+k+1);
  31.                 if(i+k+1<=n&&j-k-1>=1)ss-=getsum(i+k+1,j-k-1,i+k+1,j-k-1);
  32.                 if(i+k+1<=n&&j+k+1<=n)ss-=getsum(i+k+1,j+k+1,i+k+1,j+k+1);
  33.  
  34.                 if(ss>0)return true;
  35.             }
  36.         }
  37.         return false;
  38.  
  39.     }
  40. }
  41.  
  42. int main(){
  43.     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  44.     cin>>n>>m;
  45.  
  46.     for(int i=1;i<=n;i++){
  47.         cin>>s[i];
  48.         s[i]="#"+s[i];
  49.         for(int j=1;j<=n;j++){
  50.             if(s[i][j]=='A'){
  51.                 xa=i;
  52.                 ya=j;
  53.             }else if(s[i][j]=='B'){
  54.                 xb=i;
  55.                 yb=j;
  56.             }
  57.         }
  58.     }
  59.  
  60.     queue<pair<int,int> >q;
  61.     q.push({xb,yb});
  62.  
  63.     while(!q.empty()){
  64.         pair<int,int> e=q.front();
  65.         q.pop();
  66.         sum[e.first][e.second]=1;
  67.         for(int i=0;i<4;i++){
  68.             int newx=e.first+dx[i];
  69.             int newy=e.second+dy[i];
  70.  
  71.             if(ok(newx,newy)&&!sum[newx][newy])q.push({newx,newy});
  72.         }
  73.     }
  74.  
  75.     if(sum[xa][ya]){
  76.         cout<<-1;
  77.         return 0;
  78.     }
  79.  
  80.     for(int i=1;i<=n;i++){
  81.         for(int j=1;j<=n;j++){
  82.             sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+sum[i][j];
  83.         }
  84.     }
  85.  
  86.     q.push({xa,ya});
  87.     while(!q.empty()){
  88.         pair<int,int> e=q.front();
  89.         q.pop();
  90.         cana[e.first][e.second]=1;
  91.         for(int i=0;i<4;i++){
  92.             int newx=e.first+dx[i];
  93.             int newy=e.second+dy[i];
  94.  
  95.             if(ok(newx,newy)&&!cana[newx][newy])q.push({newx,newy});
  96.         }
  97.     }
  98.  
  99.  
  100.  
  101.  
  102.     int lo=1;
  103.     int hi=n;
  104.     int ans=n;
  105.     while(lo<=hi){
  106.         int mid=(lo+hi)>>1;
  107.         if(solve(mid)){
  108.             hi=mid-1;
  109.             ans=mid;
  110.         }else{
  111.             lo=mid+1;
  112.         }
  113.     }
  114.  
  115.     cout<<ans;
  116.     return 0;
  117. }
Success #stdin #stdout 0s 17496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/UWmcD5
language:
C++14 (gcc 8.3)
created:
5 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!