Saturday 29 July 2017

Lightoj 1175 - Jane and the Frost Giants

  1. #include <bits/stdc++.h>
  2. using namespace std; 
  3. const int fx[]={+1,-1,+0,+0};
  4. const int fy[]={+0,+0,+1,-1};
  5. char graph[201][201];
  6. int dj[201][201];
  7. int df[201][201];
  8. bool visit[201][201];
  9.  
  10. int r,c;
  11. vector<pii>fdata;
  12. pii pointj;
  13.  
  14. bool testf(pii tmp)
  15. {
  16.     if(tmp.ff<0 || tmp.ff>=|| tmp.ss<0 || tmp.ss>=|| visit[tmp.ff][tmp.ss] || graph[tmp.ff][tmp.ss]!='.')
  17.         return 0;
  18.     return 1;
  19. }
  20.  
  21. bool testj(pii tmp)
  22. {
  23.     if(tmp.ff<0 || tmp.ff>=|| tmp.ss<0 || tmp.ss>=|| visit[tmp.ff][tmp.ss] || graph[tmp.ff][tmp.ss]!='.')
  24.         return 0;
  25.     return 1;
  26. }
  27.  
  28. void bfsf()
  29. {
  30.     loop(i,r+1) loop(j,c+1)
  31.     {visit[i][j]=0;df[i][j]=inf;}
  32.  
  33.     queue<pii>Q;
  34.     pii u,v;
  35.     for(int i=0;i<SZ(fdata);i++)
  36.     {
  37.         u=fdata[i];
  38.         df[u.ff][u.ss]=0;
  39.         Q.push(u);
  40.         visit[u.ff][u.ss]=1;
  41.     }
  42.     while(!Q.empty())
  43.     {
  44.         u=Q.front();
  45.         Q.pop();
  46.         loop(i,4)
  47.         {
  48.             v.ff=u.ff+fx[i];
  49.             v.ss=u.ss+fy[i];
  50.             if(testf(v))
  51.             {
  52.                 visit[v.ff][v.ss]=1;
  53.                 df[v.ff][v.ss]=df[u.ff][u.ss]+1;
  54.                 Q.push(v);
  55.             }
  56.         }
  57.     }
  58. }
  59.  
  60. int bfsj(pii src)
  61. {
  62.     loop(i,r+1) loop(j,c+1)
  63.        {
  64.          visit[i][j]=0;
  65.          dj[i][j]=inf;
  66.        }
  67.     visit[src.ff][src.ss]=1;
  68.     pii u,v;
  69.     dj[src.ff][src.ss]=0;
  70.  
  71.     queue<pii>Q;
  72.     Q.push(src);
  73.     while(!Q.empty())
  74.     {
  75.         u=Q.front();
  76.         Q.pop();
  77.         if(u.ff==0 || u.ff==r-1 || u.ss==0 || u.ss==c-1)
  78.             return dj[u.ff][u.ss];
  79.         loop(i,4)
  80.         {
  81.             v.ff=u.ff+fx[i];
  82.             v.ss=u.ss+fy[i];
  83.             if(testj(v) && (df[v.ff][v.ss] > dj[u.ff][u.ss]+1))
  84.             {
  85.                 visit[v.ff][v.ss]=1;
  86.                 dj[v.ff][v.ss]=dj[u.ff][u.ss]+1;
  87.                 Q.push(v);
  88.             }
  89.         }
  90.     }
  91.     return -1;
  92. }
  93.  
  94.  
  95. int main()
  96. {
  97.     ///freopen("in.txt","r",stdin);
  98.     ///freopen("out.txt","w",stdout);
  99.     int t;
  100.     sf(t);
  101.     TEST_CASE(t)
  102.     {
  103.         sff(r,c);
  104.         loop(i,r) loop(j,c)
  105.         {
  106.             cin>>graph[i][j];
  107.             if(graph[i][j]=='J')
  108.                 pointj.ff=i,pointj.ss=j;
  109.             else if(graph[i][j]=='F')
  110.                 fdata.pb(MP(i,j));
  111.         }
  112.  
  113.         bfsf();
  114.         int ans=bfsj(pointj);
  115.         PRINT_CASE;
  116.         if(ans==-1)
  117.             pf("IMPOSSIBLE\n");
  118.         else
  119.             pf("%d\n",ans+1);
  120.         fdata.clear();
  121.     }
  122.     return 0;
  123. }

No comments:

Post a Comment

Most Featured Post

Lightoj 1159 - Batman

http://lightoj.com/volume_showproblem.php?problem=1159 problem analysis: First i thought of this as if s1, s2 and s3 are those three str...