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. 	int x= 1;
  39. 	for(int i=0;i<rows;i++)
  40. 	{
  41. 		for(int j=0;j<cols;j++)
  42. 		{
  43. 			if(arr[i][j]==1 && owner[i][j]==0)
  44. 			{
  45. 				performbfs(arr,owner,i,j,x);
  46. 				x++;
  47. 			}
  48. 		}
  49. 	}
  50. 	for(int i=0;i<rows;i++)
  51. 	{
  52. 		for(int j=0;j<cols;j++)
  53. 		{
  54. 			cout<<owner[i][j]<<" ";
  55. 		}
  56. 		cout<<"\n";
  57. 	}
  58. 	return 0;
  59.  
  60. }
  61.  
  62. int main() {
  63. 	// your code goes here
  64. 	vector<vector<int>> arr = {{1, 0, 0, 0, 1},  
  65. {1, 1, 0, 0, 0},  
  66. {0, 0, 0, 0, 0},  
  67. {0, 0, 1, 1, 1}};
  68. int dis = findminDist (arr);
  69. cout<<dis;
  70. return 0;
  71. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 0 0 0 2 
1 1 0 0 0 
0 0 0 0 0 
0 0 3 3 3 
0
https://ideone.com/1SRqTw
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!