fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int BFS();
  5.  
  6. char grid[30][30];
  7. int distances[30][30];
  8. int r=0,c=0,s1=0,s2=0,f1=0,f2=0;
  9. int dx[]={1,-1,0,0};
  10. int dy[]={0,0,-1,1};
  11.  
  12. set<pair<int,int>> points;//Keeps track of points
  13.  
  14. int main()
  15. {
  16. 	ios_base::sync_with_stdio(false);//FAST IO
  17. 	int t;
  18. 	cin>>t;
  19. 	while(t--)
  20. 	{
  21. 		points.clear();//clearing set
  22. 		cin>>r;//rows columns
  23. 		c=r;
  24. 		for(int i=0;i<r;i++)
  25. 		{
  26. 			string x1;
  27. 			cin>>x1;
  28. 			for(int j=0;j<c;j++)
  29. 			{
  30. 				grid[i][j]=x1[j];
  31. 				distances[i][j]=-1;
  32. 				if(x1[j]=='*')//Found treasures
  33. 				{
  34. 					pair<int, int>tmp=make_pair(i,j);
  35. 					points.insert(tmp);//adding treasures to set
  36. 				}
  37. 			}
  38. 		}//built grid
  39. 		s1=s2=0;
  40. 		distances[s1][s2]=0;//for 0,0
  41. 		int ansd=0;
  42. 		int flag=1;
  43. 		while(!points.empty())//Till treasures no more
  44.         {
  45.             for(int i=0;i<r;i++)
  46.             {
  47.                 for (int j = 0; j < c; j++)//reseting 
  48.                 {
  49.                     distances[i][j]=-1;
  50.                     if(grid[i][j]=='V')//Visited
  51.                     {
  52.                         grid[i][j]='.';//Accesibly again in next walk
  53.                     }
  54.                 }
  55.             }
  56.             distances[s1][s2]=0;//next source specified in BFS function
  57.             int dis=BFS();
  58.             if(dis!=-1)
  59.             {
  60.                 ansd += dis;
  61.             }
  62.             else
  63.             {
  64.                 cout<<"-1\n";
  65.                 flag = 0;
  66.                 break;
  67.             }
  68.         }
  69.         if(flag==1)//This means that all treasures collected. Applying BFS for (n,n)
  70.         {
  71.             for(int i11=0;i11<r;i11++)//resetting
  72.             {
  73.                 for(int j1=0;j1<c;j1++)
  74.                 {
  75.                     if(grid[i11][j1]=='V')
  76.                     {
  77.                         grid[i11][j1]='.';
  78.                     }
  79.                     distances[i11][j1]=0;
  80.                 }
  81.             }
  82.             f1=r-1;f2=c-1;
  83.             grid[f1][f2]='*';//setting destination as treasure itself
  84.             int x=BFS();
  85.             if(x!=-1)
  86.             {
  87.                 cout<<(ansd+x)<<endl;
  88.             }
  89.             else
  90.             {
  91.                 cout<<"-1\n";
  92.             }
  93.         }
  94. 	}
  95. 	return 0;
  96. }
  97.  
  98. int BFS()
  99. {
  100.     queue<pair<int,int>> q;//Queue for BFS
  101.     pair<int,int> src=make_pair(s1,s2);//source coordinates
  102.     q.push(src);
  103.     while(!q.empty())
  104.     {
  105.         pair<int,int> p=q.front();
  106.         q.pop();
  107.         for(int i=0;i<4;i++)
  108.         {
  109.             if(((p.first+dx[i]>=0)&&(p.first+dx[i]<r))&&((p.second+dy[i]>=0)&&(p.second+dy[i]<c))&&(grid[p.first+dx[i]][p.second+dy[i]]!='#'))
  110.             {//If point is in range and is valid
  111.                 int cx,cy;
  112.                 cx=p.first+dx[i];
  113.                 cy=p.second+dy[i];
  114.                 distances[cx][cy]=distances[p.first][p.second]+1;//Distances
  115.                 if(grid[cx][cy]=='*')//destination
  116.                 {
  117.                     for(pair<int,int> rm:points)
  118.                     {
  119.                         if(rm.first==cx&&rm.second==cy)// Finding the node and removing it
  120.                         {
  121.                             points.erase(rm);
  122.                             break;
  123.                         }
  124.                     }
  125.                     grid[cx][cy]='.';//It is walkable again
  126.                     s1=cx;s2=cy;//next source set
  127.                     return distances[cx][cy];
  128.                 }
  129.                 else if(grid[cx][cy]=='.')//Normal tile. Now setting to visited
  130.                 {
  131.                     grid[cx][cy]='V';//Adding to visited
  132.                     pair<int,int> temp=make_pair(cx,cy);
  133.                     q.push(temp);
  134.                 }
  135.             }
  136.         }
  137.     }
  138.     return -1;
  139. }
Success #stdin #stdout 0s 3288KB
comments (?)
stdin
copy 
4

3
...
.##
*#.

3
..*
...
...

3
..*
*..
...

4
....
.#.*
.#*.
**#.
stdout
copy 
-1
4
6
16
https://ideone.com/gsCSSL
language:
C++14 (gcc 8.3)
created:
9 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!