Advertisement
Saleh127

Light OJ 1066 / BFS-DFS

Nov 2nd, 2021
1,914
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-02-01.42.21
  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.  
  19. ll n,m,xx,yy;
  20.  
  21. bool valid(ll x,ll y,char c)
  22. {
  23.      return (x>=0 && x<n && y>=0 && y<n && v[x][y]==0 && (a[x][y]!='#' && (a[x][y]=='.' || a[x][y]==c)));
  24. }
  25.  
  26. ll bfs(ll x,ll y,char c)
  27. {
  28.      memset(v,0,sizeof v);
  29.  
  30.      queue<pair<pair<ll,ll>,ll>>q;
  31.  
  32.      q.push({{x,y},0ll});
  33.  
  34.      v[x][y]=1;
  35.      a[x][y]='.';
  36.  
  37.      while(q.empty()==false)
  38.      {
  39.           auto d=q.front();
  40.  
  41.           q.pop();
  42.  
  43.           if(a[d.first.first][d.first.second]==c)
  44.           {
  45.                xx=d.first.first;
  46.                yy=d.first.second;
  47.  
  48.                return d.second;
  49.           }
  50.  
  51.           for(ll i=0;i<4;i++)
  52.           {
  53.                x=dx[i]+d.first.first;
  54.                y=dy[i]+d.first.second;
  55.  
  56.                if(valid(x,y,c))
  57.                {
  58.                     v[x][y]=1;
  59.                     q.push({{x,y},d.second+1});
  60.                }
  61.           }
  62.      }
  63.  
  64.      return -1;
  65. }
  66.  
  67. int main()
  68. {
  69.    ios_base::sync_with_stdio(0);
  70.    cin.tie(0);cout.tie(0);
  71.  
  72.  
  73.    test
  74.    {
  75.         ll i,j,k,l,food=0,ans=0;
  76.  
  77.         char c='B';
  78.  
  79.         cin>>n;
  80.  
  81.         for(i=0;i<n;i++)
  82.         {
  83.              for(j=0;j<n;j++)
  84.              {
  85.                   cin>>a[i][j];
  86.  
  87.                   if(a[i][j]>='A' && a[i][j]<='Z')
  88.                   {
  89.                        if(a[i][j]=='A')
  90.                        {
  91.                             xx=i;
  92.                             yy=j;
  93.                        }
  94.                        else food++;
  95.                   }
  96.              }
  97.         }
  98.  
  99.         while(food--)
  100.         {
  101.              l=bfs(xx,yy,c++);
  102.              if(l==-1)
  103.              {
  104.                   ans=-1;
  105.                   break;
  106.              }
  107.              ans+=l;
  108.         }
  109.  
  110.         cout<<"Case "<<cs<<": ";
  111.  
  112.         if(ans==-1) cout<<"Impossible"<<nl;
  113.         else cout<<ans<<nl;
  114.    }
  115.  
  116.  
  117.    get_lost_idiot;
  118. }
  119.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement