fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int,int> ii;
  4. int R,C;
  5.  bool check(int x,int y){
  6. return (x==0||y==0||x>R||y>C);
  7.  
  8.  
  9. }
  10. int main(){
  11. 	int t;
  12. 	cin>>t;
  13. 	while(t--){
  14. cin>>R>>C;
  15. pair<int,int> fire,joey;
  16. bool b[R+1][C+1];
  17. memset(b,0,sizeof b);
  18. queue<pair<pair<int,int>,int> > q;
  19. for(int i=0;i<R;i++)
  20. for(int j=0;j<C;j++){
  21. 	char c;
  22. 	cin>>c;
  23. 	if(c=='#') b[i+1][j+1]=1;
  24. 	else if(c=='.') b[i+1][j+1]=0;
  25. 	else if(c=='J') joey=make_pair(i+1,j+1),b[i+1][j+1]=1;
  26. 	else q.push(make_pair(ii(i+1,j+1),1e9)),b[i+1][j+1]=2;
  27. }
  28.  
  29. q.push(make_pair(joey,0));
  30. int dist=1e9;
  31. while(!q.empty()){
  32.  
  33. auto Q=q.front();
  34. q.pop();
  35. pair<int,int> c=Q.first;
  36. int x=c.first,y=c.second,z=Q.second;
  37. if(check(x,y)) {dist=min(min(z,1000000000),dist);continue;}
  38. if(check(x+1,y)||!b[x+1][y]) {q.push(make_pair(ii(x+1,y),z+1));if(!check(x+1,y)) b[x+1][y]=1;}
  39. if(check(x-1,y)||!b[x-1][y]) {q.push(make_pair(ii(x-1,y),z+1));if(!check(x-1,y)) b[x-1][y]=1;}
  40. if(check(x,y+1)||!b[x][y+1]) {q.push(make_pair(ii(x,y+1),z+1));if(!check(x,y+1)) b[x][y+1]=1;}
  41. if(check(x,y-1)||!b[x][y-1]) {q.push(make_pair(ii(x,y-1),z+1));if(!check(x+1,y)) b[x][y-1]=1;}
  42.  
  43. }
  44. if(dist==1000000000) cout<<"IMPOSSIBLE"<<endl;
  45. else cout<<dist<<endl;
  46.  
  47. 	}
  48. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qLt4eF
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!