fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. #define ll long long
  5. #define pii pair<int,int>
  6. #define pill pair<int,ll>
  7. #define pll pair<ll,ll>
  8. #define pb push_back
  9. #define fi first
  10. #define se second
  11. #define ff fi.fi
  12. #define fs fi.se
  13. #define sf se.fi
  14. #define ss se.se
  15. #define MASK(x) (((1)<<(x))-1)
  16. #define getbit(x,k) (((x)>>(k))&1)
  17.  
  18. using namespace std;
  19.  
  20. const int maxn=1e3+50,mod=1e9+7;
  21. const ll inf=0x3f3f3f3f3f3f3f3f;
  22.  
  23. int n,m,k;
  24. char A[maxn][maxn],B[maxn][maxn];
  25. int xs,ys,xst,yst,xen,yen;
  26. int tim[maxn][maxn];
  27. int dx[]={0,0,-1,1},dy[]={1,-1,0,0};
  28. int d[maxn][maxn];
  29.  
  30. void bfs01()
  31. {
  32.     memset(d,0x3f,sizeof d);
  33.     deque<pii>dQ;
  34.     dQ.push_front({xst,yst});
  35.     d[xst][yst]=0;
  36.     while(dQ.size())
  37.     {
  38.         pii u=dQ.front();dQ.pop_front();
  39.         for(int k=0;k<4;k++)
  40.         {
  41.             int nx=u.fi+dx[k],ny=u.se+dy[k];
  42.             if(nx<1 || nx>n || ny<1 || ny>m) continue;
  43.             int c=(B[nx][ny]=='S');
  44.             if(d[u.fi][u.se]+c<d[nx][ny])
  45.             {
  46.                 d[nx][ny]=d[u.fi][u.se]+c;
  47.                 if(c==0) dQ.push_front({nx,ny});
  48.                 else dQ.push_back({nx,ny});
  49.             }
  50.         }
  51.     }
  52. }
  53. bool check(int t)
  54. {
  55.     for(int i=1;i<=n;i++)
  56.         for(int j=1;j<=m;j++)
  57.             B[i][j]=A[i][j];
  58.     memset(tim,0,sizeof tim);
  59.     queue<pii>Q;
  60.     for(int i=1;i<=n;i++)
  61.         for(int j=1;j<=m;j++)
  62.             if(B[i][j]=='S') Q.push({i,j}),tim[i][j]=1;
  63.     if(t)
  64.     {
  65.         while(Q.size())
  66.         {
  67.             pii u=Q.front();Q.pop();
  68.             B[u.fi][u.se]='S';
  69.             for(int k=0;k<4;k++)
  70.             {
  71.                 int nx=u.fi+dx[k],ny=u.se+dy[k];
  72.                 if(nx<1 || nx>n || ny<1 || ny>m) continue;
  73.                 if(tim[nx][ny]) continue;
  74.                 if(B[nx][ny]!='.') continue;
  75.                 if(tim[u.fi][u.se]<t)
  76.                 {
  77.                     tim[nx][ny]=tim[u.fi][u.se]+1;
  78.                     Q.push({nx,ny});
  79.                 }
  80.             }
  81.         }
  82.     }
  83.     bfs01();
  84.     return d[xen][yen]<=k;
  85. }
  86. int main()
  87. {
  88.     cin>>n>>m>>k;
  89.     for(int i=1;i<=n;i++)
  90.         for(int j=1;j<=m;j++)
  91.         {
  92.             cin>>A[i][j];
  93.             if(A[i][j]=='H') xst=i,yst=j;
  94.             if(A[i][j]=='G') xen=i,yen=j;
  95.         }
  96.     int l=0,r=1e6,mid,ans=0;
  97.     while(l<=r)
  98.     {
  99.         mid=(l+r)/2;
  100.         if(check(mid)) l=mid+1,ans=mid;
  101.         else r=mid-1;
  102.     }
  103.     if(ans==1e6) ans=-1;
  104.     cout<<ans;
  105. }
  106. /*
  107. 5 5 1
  108. H....
  109. .....
  110. .....
  111. S....
  112. ....G
  113. */
  114.  
Success #stdin #stdout 0.01s 12160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/UGnmSV
language:
C++14 (gcc 8.3)
created:
4 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!