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