Lightoj 1175 - Jane and the Frost Giants

http://lightoj.com/volume_showproblem.php?problem=1175

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>=r || tmp.ss<0 || tmp.ss>=c || 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>=r || tmp.ss<0 || tmp.ss>=c || 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. }