fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. vector<vector<int>> dir = {{0,1},{1,0},{-1,0},{0,-1}};
  6.  
  7. void performbfs (vector<vector<int>> & arr ,vector<vector<int>> & owner,int i,int j,int x)
  8. {
  9.  
  10. 	queue<pair<int,int>> q;
  11. 	q.push({i,j});
  12. 	owner[i][j]=x;
  13. 	while(q.size()!=0)
  14. 	{
  15. 		auto it = q.front();
  16. 		q.pop();
  17. 		int currI = it.first;
  18. 		int currJ = it.second;
  19. 		for(int k=0;k<4;k++)
  20. 		{
  21. 			int newI = currI + dir[k][0];
  22. 			int newJ = currJ + dir[k][1];
  23. 		if(newI>=0 && newI<arr.size() && newJ >=0 && newJ <arr[0].size() && arr[newI][newJ]==1 && owner[newI][newJ]==0)
  24. 		{
  25. 			owner[newI][newJ]=x;
  26. 			q.push({newI,newJ});
  27. 		}
  28.  
  29. 		}
  30. 	}
  31. }
  32.  
  33. int findminDist (	vector<vector<int>> &arr)
  34. {
  35. 	int rows = arr.size();
  36. 	int cols = arr[0].size();
  37. 	vector<vector<int>> owner (rows,vector<int>(cols,0));
  38. 	vector<vector<int>> distance (rows,vector<int>(cols,-1));
  39. 	int x= 1;
  40. 	for(int i=0;i<rows;i++)
  41. 	{
  42. 		for(int j=0;j<cols;j++)
  43. 		{
  44. 			if(arr[i][j]==1 && owner[i][j]==0)
  45. 			{
  46. 				performbfs(arr,owner,i,j,x);
  47. 				x++;
  48. 			}
  49. 		}
  50. 	}
  51. 	queue<pair<int,int>> q;
  52. 	for(int i=0;i<rows;i++)
  53. 	{
  54. 		for(int j=0;j<cols;j++)
  55. 		{
  56. 			if(arr[i][j]==1)
  57. 			{
  58. 					q.push({i,j});
  59. 					distance[i][j]=0;
  60. 			}
  61. 		}
  62. 	}
  63. 	int mindist = INT_MAX;
  64. 	while(q.size()!=0)
  65. 	{
  66. 		auto it = q.front();
  67. 		q.pop();
  68. 		int currI = it.first;
  69. 		int currJ = it.second;
  70. 		for(int k=0;k<4;k++)
  71. 		{
  72. 			int newI = currI + dir[k][0];
  73. 			int newJ = currJ + dir[k][1];
  74. 		if(newI>=0 && newI<arr.size() && newJ >=0 && newJ <arr[0].size())
  75. 		{
  76. 			if(distance[newI][newJ]==-1)
  77. 			{
  78. 				distance[newI][newJ] = distance[currI][currJ] +1;
  79. 				owner[newI][newJ] = owner[currI][currJ]; 
  80. 				q.push({newI,newJ});
  81. 			}
  82. 			else
  83. 			{
  84. 				if (owner[newI][newJ] != owner[currI][currJ])
  85. 				{
  86. 					mindist = min (distance[newI][newJ]+distance[currI][currJ],mindist);
  87. 				}
  88. 			}
  89. 		}
  90.  
  91. 		}
  92. 	}
  93.  
  94. 	return mindist;
  95.  
  96. }
  97.  
  98. int main() {
  99. 	// your code goes here
  100. 	vector<vector<int>> arr = {{1, 0, 0, 0, 1},  
  101. {1, 1, 0, 0, 0},  
  102. {0, 0, 0, 0, 0},  
  103. {0, 0, 1, 1, 1}};
  104. int dis = findminDist (arr);
  105. cout<<dis;
  106. return 0;
  107. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
https://ideone.com/ZAKGN9
language:
C++ (gcc 8.3)
created:
1 hour 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!