0
Answer

How to get the coordinates of each cluster using c++

Dev Teywa

Dev Teywa
4y
536
1
Hello everyone, can someone help me to solve this problem .
 
In my script i count number of cluster in this matrix, but i need to return the coordinates x,y of each cluster founded.
  1. #include <bits/stdc++.h>  
  2. using namespace std;  
  3. // 2D array for the storing the horizontal and vertical  
  4. // directions. (Up, left, down, right}  
  5. vector<vector<int> > dirs = { { 0, -1 },  
  6. { -1, 0 },  
  7. { 0, 1 },  
  8. { 1, 0 } };  
  9. // Function to perform dfs of the input grid  
  10. void dfs(vector<vector<int> >& grid, int x0, int y0,  
  11. int i, int j, vector<pair<int, int> >& v)  
  12. {  
  13. int rows = grid.size(), cols = grid[0].size();  
  14. if (i < 0 || i >= rows || j < 0  
  15. || j >= cols || grid[i][j] <= 0)  
  16. return;  
  17. // marking the visited element as -1  
  18. grid[i][j] *= -1;  
  19. // computing coordinates with x0, y0 as base  
  20. v.push_back({ i - x0, j - y0 });  
  21. // repeat dfs for neighbors  
  22. for (auto dir : dirs) {  
  23. dfs(grid, x0, y0, i + dir[0], j + dir[1], v);  
  24. }  
  25. }  
  26. // Main function that returns distinct count of islands in  
  27. // a given boolean 2D matrix  
  28. int countDistinctIslands(vector<vector<int> >& grid)  
  29. {  
  30. int rows = grid.size();  
  31. if (rows == 0)  
  32. return 0;  
  33. int cols = grid[0].size();  
  34. if (cols == 0)  
  35. return 0;  
  36. set<vector<pair<int, int> > > coordinates;  
  37. for (int i = 0; i < rows; ++i) {  
  38. for (int j = 0; j < cols; ++j) {  
  39. // If a cell is not 1  
  40. // no need to dfs  
  41. if (grid[i][j] != 1)  
  42. continue;  
  43. // vector to hold coordinates  
  44. // of this island  
  45. vector<pair<int, int> > v;  
  46. dfs(grid, i, j, i, j, v);  
  47. // insert the coordinates for  
  48. // this island to set  
  49. coordinates.insert(v);  
  50. }  
  51. }  
  52. return coordinates.size();  
  53. }  
  54. // Driver code  
  55. int main()  
  56. {  
  57. vector<vector<int> > grid = {{0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1},  
  58. {0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0},  
  59. {1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0},  
  60. {0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0},  
  61. {0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0},  
  62. {1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1},  
  63. {0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0},  
  64. {1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0},  
  65. {0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1},  
  66. {1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1}};  
  67. cout << "Number of distinct islands is "  
  68. << countDistinctIslands(grid);  
  69. return 0;  
  70. }  
Next Recommended Forum