fork download
copy 
  1. /*
  2.  
  3.  
  4.                  """Bismillahir Rahmanur Rahim"""
  5.  
  6. */
  7. #include<bits/stdc++.h>
  8. using namespace std;
  9. #define pi 2*acos(0.0)
  10. #define ll long long int
  11. #define pb push_back
  12. #define pf push_front
  13. const ll sz = 1000001;
  14. #define mp make_pair
  15. #define ses '\n'
  16. #define stm istringstream
  17. #define gcd __gcd
  18. ll lcm(ll x,ll y){return (x*y)/gcd(x,y);}
  19. #define tin ll T;cin>>T; for(ll o=1;o<=T;o++)
  20. #define tout cout<<"Case "<<o<<": ";
  21. ll dr[]={-1,0,1,0};
  22. ll dc[]={0,1,0,-1};
  23. ll valid(ll r,ll c,ll x,ll y)
  24. {
  25.     if(r>=0 && r<x && c>=0 && c<y)
  26.         return 1;
  27.     else return 0;
  28. }
  29. ll ar[20][20];
  30. int bfs(ll a,ll b,ll x,ll y)
  31. {
  32.     ll dis[x][y]={},vis[x][y]={};
  33.      queue<pair<ll,ll> >q;
  34.         q.push({a,b});
  35.         vis[a][b]=1;
  36.         dis[a][b]=0;
  37.         while(!q.empty())
  38.           {
  39.              ll p,k;
  40.              p=q.front().first;
  41.              k=q.front().second;
  42.              q.pop();
  43.              if(ar[p][k]==3)
  44.                 return dis[p][k];
  45.              for(int i=0;i<4;i++)
  46.              {
  47.                  ll r=p+dr[i];
  48.                  ll c=k+dc[i];
  49.  
  50.                  if(valid(r,c,x,y))
  51.                  {
  52.                      if(vis[r][c]==0)
  53.                      {
  54.                          if(ar[r][c]==1 || ar[r][c]==3)
  55.                             {
  56.                                 vis[r][c]=1;
  57.                                 dis[r][c]=dis[p][k]+1;
  58.                                q.push({r,c});
  59.                             }
  60.                      }
  61.                  }
  62.              }
  63.           }
  64. }
  65.  
  66. int main()
  67. {
  68.     //freopen ("input.txt","r",stdin);
  69.     //freopen ("output.txt","w",stdout);
  70. tin
  71.     {
  72.         ll x,y,a,b,p1,p2,q1,q2,r1,r2;
  73.         cin>>x>>y;
  74.         char c;
  75.         for(int i=0;i<x;i++)
  76.             for(int j=0;j<y;j++)
  77.             {
  78.                 cin>>c;
  79.                 if(c=='.')
  80.                     ar[i][j]=1;
  81.                 if(c=='#' || c=='m')
  82.                     ar[i][j]=2;
  83.                 if(c=='h')
  84.                 {
  85.                     ar[i][j]=3;
  86.                     a=i;
  87.                     b=j;
  88.                 }
  89.                 if(c=='a')
  90.                 {
  91.                     ar[i][j]=1;
  92.                     p1=i;
  93.                     p2=j;
  94.                 }
  95.                 if(c=='b')
  96.                 {
  97.                     ar[i][j]=1;
  98.                     q1=i;
  99.                     q2=j;
  100.                 }
  101.                 if(c=='c')
  102.                 {
  103.                     ar[i][j]=1;
  104.                     r1=i;
  105.                     r2=j;
  106.                 }
  107.             }
  108.  
  109. ll z=bfs(p1,p2,x,y);
  110. ll z1=bfs(q1,q2,x,y);
  111. ll z2=bfs(r1,r2,x,y);
  112.       tout; cout<<max(z,max(z1,z2))<<ses;
  113.     }
  114.     return 0;
  115. }
  116. /*   --------------------
  117.     |      ~SOHAN~       |
  118.     |   ~Chandler68~     |
  119.      --------------------
  120.     || VALAR MORGULIS||==|| ALL MEN MUST DIE ||
  121.     \\ Power Is Power//
  122.     || I Can Do This All day ||
  123.     // We are on a Break \\ // How you doin'? \\
  124.     || Say My Name || ~~ || I Am The Who Knocks ||
  125.     // I Am Ted Mosby Architect \\
  126.     || It Is Legen --wait for it -- dary ,Legendary ||
  127.     \\ Penny - Penny - Penny // -- Bazinga
  128.  
  129. */
  130.  
Time limit exceeded #stdin #stdout 5s 4540KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ICbpHE
language:
C++14 (gcc 8.3)
created:
4 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!