Advertisement
Saleh127

Light OJ 1046 / BFS-DFS

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