fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define ll long long
  5. #define N int(1e6)
  6. using namespace std;
  7. ll r, c;
  8. ll dx[4]= {1, -1, 0, 0};
  9. ll dy[4]= {0, 0, 1, -1};
  10. char a[55][55];
  11. ll tg[55][55],kc[55][55];
  12. bool vis[55][55];
  13. bool bien(ll x,ll y)
  14. {
  15.     return (x<=r && y<=c && x>=1 && y>=1);
  16. }
  17. bool ok;
  18. void bfs(ll x, ll y)
  19. {
  20.     memset(vis,0,sizeof vis);
  21.     queue<pair<ll, ll>>q;
  22.     q.push({x, y});
  23.     vis[x][y]=1;
  24.     tg[x][y]=0;
  25.     //cout<<x<<" "<<y<<'\n';
  26.     while(!q.empty())
  27.     {
  28.         auto top=q.front();
  29.         q.pop();
  30.         for(int i=0; i<=3; i++)
  31.         {
  32.             ll nx=top.fi+dx[i];
  33.             ll ny=top.se+dy[i];
  34.             if(!vis[nx][ny] && a[nx][ny]=='.' && bien(nx,ny))
  35.             {
  36.                 //cout<<nx<<" "<<ny<<'\n';
  37.                 tg[nx][ny]=min(tg[nx][ny],tg[top.fi][top.se]+1);
  38.                 vis[nx][ny]=1;
  39.                 q.push({nx,ny});
  40.             }
  41.         }
  42.     }
  43. }
  44. void bfs1(ll x,ll y)
  45. {
  46.     memset(vis,0,sizeof vis);
  47.     queue<pair<ll, ll>>q;
  48.     q.push({x, y});
  49.     vis[x][y]=1;
  50.     kc[x][y]=0;
  51.     //cout<<x<<" "<<y<<'\n';
  52.     while(!q.empty())
  53.     {
  54.         auto top=q.front();
  55.         q.pop();
  56.         for(int i=0; i<=3; i++)
  57.         {
  58.             ll nx=top.fi+dx[i];
  59.             ll ny=top.se+dy[i];
  60.             if(a[nx][ny]=='D' && (kc[top.fi][top.se]+1)<tg[nx][ny])
  61.             {
  62.                 ok=1;
  63.                 //cout<<"  "<<nx<< " "<<ny<<'\n';
  64.                 kc[nx][ny]=kc[top.fi][top.se]+1;
  65.                 cout<<kc[nx][ny];
  66.                 return ;
  67.             }
  68.             if(!vis[nx][ny] && a[nx][ny]=='.' && bien(nx,ny) && (kc[top.fi][top.se]+1)<tg[nx][ny])
  69.             {
  70.                 kc[nx][ny]=min(kc[nx][ny],kc[top.fi][top.se]+1);
  71.                 //cout<<nx<<" "<<ny<<" "<<kc[nx][ny]<<'\n';
  72.                 vis[nx][ny]=1;
  73.                 q.push({nx,ny});
  74.             }
  75.         }
  76.     }
  77. }
  78. pair<ll,ll>bd;
  79. int main()
  80. {
  81.     ios::sync_with_stdio(0);
  82.     cin.tie(0);
  83.     cout.tie(0);
  84.  
  85.     cin>>r>>c;
  86.     for(int i=1; i<=r; i++)
  87.         for(int j=1; j<=c; j++)
  88.         {
  89.             tg[i][j]=LLONG_MAX;
  90.             kc[i][j]=LLONG_MAX;
  91.             cin>>a[i][j];
  92.             if(a[i][j]=='S') bd={i,j};
  93.         }
  94.     //cout<<bd.fi<<" "<<bd.se<<'\n'<<kt.fi<<" "<<kt.se;
  95.     for(int i=1; i<=r; i++)
  96.         for(int j=1; j<=c; j++)
  97.             if(a[i][j]=='*') bfs(i, j);
  98.  
  99. //    for(int i=1; i<=r; i++)
  100. //    {
  101. //        for(int j=1; j<=c; j++)
  102. //        {
  103. //            //cout<<a[i][j]<<" ";
  104. //            if(a[i][j]=='*') cout<<0<<" ";
  105. //            else if(a[i][j]=='.') cout<<tg[i][j]<<" ";
  106. //            else cout<<a[i][j]<<" ";
  107. //        }
  108. //        cout<<'\n';
  109. //    }
  110.     bfs1(bd.fi,bd.se);
  111.     if(ok==0) cout<<"KAKTUS";
  112.  
  113.     return 0;
  114. }
  115.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
KAKTUS
https://ideone.com/DPyhEl
language:
C++ (gcc 8.3)
created:
2 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!