- #include <bits/stdc++.h>
- using namespace std;
- const int fx[]={+1,-1,+0,+0};
- const int fy[]={+0,+0,+1,-1};
- char graph[201][201];
- int dj[201][201];
- int df[201][201];
- bool visit[201][201];
- int r,c;
- vector<pii>fdata;
- pii pointj;
- bool testf(pii tmp)
- {
- if(tmp.ff<0 || tmp.ff>=r || tmp.ss<0 || tmp.ss>=c || visit[tmp.ff][tmp.ss] || graph[tmp.ff][tmp.ss]!='.')
- return 0;
- return 1;
- }
- bool testj(pii tmp)
- {
- if(tmp.ff<0 || tmp.ff>=r || tmp.ss<0 || tmp.ss>=c || visit[tmp.ff][tmp.ss] || graph[tmp.ff][tmp.ss]!='.')
- return 0;
- return 1;
- }
- void bfsf()
- {
- loop(i,r+1) loop(j,c+1)
- {visit[i][j]=0;df[i][j]=inf;}
- queue<pii>Q;
- pii u,v;
- for(int i=0;i<SZ(fdata);i++)
- {
- u=fdata[i];
- df[u.ff][u.ss]=0;
- Q.push(u);
- visit[u.ff][u.ss]=1;
- }
- while(!Q.empty())
- {
- u=Q.front();
- Q.pop();
- loop(i,4)
- {
- v.ff=u.ff+fx[i];
- v.ss=u.ss+fy[i];
- if(testf(v))
- {
- visit[v.ff][v.ss]=1;
- df[v.ff][v.ss]=df[u.ff][u.ss]+1;
- Q.push(v);
- }
- }
- }
- }
- int bfsj(pii src)
- {
- loop(i,r+1) loop(j,c+1)
- {
- visit[i][j]=0;
- dj[i][j]=inf;
- }
- visit[src.ff][src.ss]=1;
- pii u,v;
- dj[src.ff][src.ss]=0;
- queue<pii>Q;
- Q.push(src);
- while(!Q.empty())
- {
- u=Q.front();
- Q.pop();
- if(u.ff==0 || u.ff==r-1 || u.ss==0 || u.ss==c-1)
- return dj[u.ff][u.ss];
- loop(i,4)
- {
- v.ff=u.ff+fx[i];
- v.ss=u.ss+fy[i];
- if(testj(v) && (df[v.ff][v.ss] > dj[u.ff][u.ss]+1))
- {
- visit[v.ff][v.ss]=1;
- dj[v.ff][v.ss]=dj[u.ff][u.ss]+1;
- Q.push(v);
- }
- }
- }
- return -1;
- }
- int main()
- {
- ///freopen("in.txt","r",stdin);
- ///freopen("out.txt","w",stdout);
- int t;
- sf(t);
- TEST_CASE(t)
- {
- sff(r,c);
- loop(i,r) loop(j,c)
- {
- cin>>graph[i][j];
- if(graph[i][j]=='J')
- pointj.ff=i,pointj.ss=j;
- else if(graph[i][j]=='F')
- fdata.pb(MP(i,j));
- }
- bfsf();
- int ans=bfsj(pointj);
- PRINT_CASE;
- if(ans==-1)
- pf("IMPOSSIBLE\n");
- else
- pf("%d\n",ans+1);
- fdata.clear();
- }
- return 0;
- }
Saturday 29 July 2017
Lightoj 1175 - Jane and the Frost Giants
Subscribe to:
Post Comments (Atom)
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...
-
Problem link: Problem Analysis: It is actually a basic Bisection problem , as we can see here we can not actually find a formula fo...
-
http://lightoj.com/volume_showproblem.php?problem=1382 Problem analysis: This is a rare problem i wrote about so far. After much strugg...
No comments:
Post a Comment