On 16.07.2017 12:37, kerdemdemir wrote:
My goal is to find connected components in a 2D array for example
finding connected '*'
chars below.
x x x x x x
x x x x x x
x x * * x x
x x * * x x
x x x * * x
* x x x x x
There are two connected '*' group in this example. First group is
composes of six '*' located closer to middle and the second group
composes only one '*' char located in the left bottom corner.
Do to this I generally implement a recursive algorithm which repeat
calling the same function by checking all neighbors around the current
index. I generally end up with something like :
void foo( int row, int col)
{
//Do something here like caching the index
if ( twoDimensionData[row - 1][col] == '*')
foo(row- 1, col);
else if ( twoDimensionData[row + 1][col] == '*')
foo(row+ 1, col);
else if ( twoDimensionData[row - 1 ][col - 1] == '*')
foo(row - 1, col - 1);
//..... I need 5 more of this bad boys I mean if checks
}
...
It is wrong to explore in only one direction, so I assume you do not
mean "else".
Is there any better way to achieve this
foreach(i;row-1..row+2){
foreach(j;col-1..col+2){
if(i==row && j==col) continue;
if(twoDimensionData[i][j] == '*')
foo(row,col);
}
}
with cool std functions like
enumerate or iota without needing to write eight if checks?
cartesianProduct(iota(row-1,row+2),iota(col-1,col+2))
.filter!(a=>(a[0]!=row||a[1]!=col))
.filter!(a=>twoDimensionData[a[0]][a[1]]=='*')
.each!(a=>foo(a.expand));
(You can usually drop the first filter because "doing something" will
usually involve checking if the node has been visited and returning or
else marking the node as visited.)