Why Join
Become a member
Login
No unread comment.
View All Comments
No unread message.
View All Messages
No unread notification.
View All Notifications
Answers
Post
An Article
A Blog
A News
A Video
An EBook
An Interview Question
Ask Question
C# Corner Home
Technologies
MonthlyLeaders
ASK A QUESTION
Forumguidelines
Dev Maroua
1.7k
244
24.7k
How to get the coordinates of each cluster using c++
Nov 4 2020 1:59 AM
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.
#include <bits/stdc++.h>
using
namespace
std;
// 2D array for the storing the horizontal and vertical
// directions. (Up, left, down, right}
vector<vector<
int
> > dirs = { { 0, -1 },
{ -1, 0 },
{ 0, 1 },
{ 1, 0 } };
// Function to perform dfs of the input grid
void
dfs(vector<vector<
int
> >& grid,
int
x0,
int
y0,
int
i,
int
j, vector<pair<
int
,
int
> >& v)
{
int
rows = grid.size(), cols = grid[0].size();
if
(i < 0 || i >= rows || j < 0
|| j >= cols || grid[i][j] <= 0)
return
;
// marking the visited element as -1
grid[i][j] *= -1;
// computing coordinates with x0, y0 as base
v.push_back({ i - x0, j - y0 });
// repeat dfs for neighbors
for
(auto dir : dirs) {
dfs(grid, x0, y0, i + dir[0], j + dir[1], v);
}
}
// Main function that returns distinct count of islands in
// a given boolean 2D matrix
int
countDistinctIslands(vector<vector<
int
> >& grid)
{
int
rows = grid.size();
if
(rows == 0)
return
0;
int
cols = grid[0].size();
if
(cols == 0)
return
0;
set<vector<pair<
int
,
int
> > > coordinates;
for
(
int
i = 0; i < rows; ++i) {
for
(
int
j = 0; j < cols; ++j) {
// If a cell is not 1
// no need to dfs
if
(grid[i][j] != 1)
continue
;
// vector to hold coordinates
// of this island
vector<pair<
int
,
int
> > v;
dfs(grid, i, j, i, j, v);
// insert the coordinates for
// this island to set
coordinates.insert(v);
}
}
return
coordinates.size();
}
// Driver code
int
main()
{
vector<vector<
int
> > grid = {{0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1},
{0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0},
{1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0},
{0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0},
{0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0},
{1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1},
{0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0},
{1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0},
{0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1},
{1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1}};
cout <<
"Number of distinct islands is "
<< countDistinctIslands(grid);
return
0;
}
Reply
Answers (
0
)
else if program
how I can grab the mouse move even when I don't press a mouse button?