Advertisement
Saleh127

Light OJ 1238 / BFS-DFS

Nov 1st, 2021
747
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-01-19.47.59
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. ll dx[]={1,-1,0,0};
  13. ll dy[]={0,0,1,-1};
  14.  
  15. char a[25][25];
  16.  
  17. bool v[25][25];
  18. ll dis[25][25];
  19. ll n,m;
  20.  
  21. bool valid(ll x,ll y)
  22. {
  23.      return (x>=0 && x<n && y>=0 && y<m && a[x][y]!='m' && a[x][y]!='#');
  24. }
  25.  
  26. void bfs(ll x,ll y)
  27. {
  28.      queue<pair<ll,ll>>q;
  29.  
  30.      q.push({x,y});
  31.      v[x][y]=1;
  32.      dis[x][y]=0;
  33.  
  34.      while(q.empty()==false)
  35.      {
  36.           pair<ll,ll> d=q.front();
  37.  
  38.           q.pop();
  39.  
  40.           for(ll i=0;i<4;i++)
  41.           {
  42.                x=dx[i]+d.first;
  43.                y=dy[i]+d.second;
  44.  
  45.                if(valid(x,y)==0 || v[x][y]==1) continue;
  46.  
  47.                dis[x][y]=dis[d.first][d.second]+1;
  48.                v[x][y]=1;
  49.                q.push({x,y});
  50.           }
  51.  
  52.      }
  53. }
  54.  
  55. int main()
  56. {
  57.    ios_base::sync_with_stdio(0);
  58.    cin.tie(0);cout.tie(0);
  59.  
  60.  
  61.    test
  62.    {
  63.         cin>>n>>m;
  64.  
  65.         ll i,j,x,y,ans=0;
  66.  
  67.         for(i=0;i<n;i++)
  68.         {
  69.              for(j=0;j<m;j++)
  70.              {
  71.                   cin>>a[i][j];
  72.                   if(a[i][j]=='h')
  73.                   {
  74.                        x=i;
  75.                        y=j;
  76.                   }
  77.              }
  78.         }
  79.  
  80.         memset(v,0,sizeof v);
  81.         memset(dis,0,sizeof dis);
  82.  
  83.         bfs(x,y);
  84.  
  85.         for(i=0;i<n;i++)
  86.         {
  87.              for(j=0;j<m;j++)
  88.              {
  89.                   if(a[i][j]>='a' &&  a[i][j]<='c')
  90.                   {
  91.                        ans=max(ans,dis[i][j]);
  92.                   }
  93.              }
  94.         }
  95.  
  96.  
  97.         cout<<"Case "<<cs<<": "<<ans<<nl;
  98.    }
  99.  
  100.  
  101.    get_lost_idiot;
  102. }
  103.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement