On 16.07.2017 18:55, Timon Gehr wrote:
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.)

Ivan's example in this style:

import std.stdio, std.range, std.algorithm, std.array;
char[][] arr;
int componentSize(size_t row, size_t col){
    if(row>=arr.length||col>=arr[row].length||arr[row][col]!='*')
        return 0;
    arr[row][col]='x';
    return 1+cartesianProduct(iota(row-1,row+2),iota(col-1,col+2))
        .map!(a=>componentSize(a.expand)).sum;
}
void main (){
    arr=["xxxxxx*",
         "xxxx*xx",
         "xx**xxx",
         "xx**x**",
         "xxxxxxx"].map!dup.array;
    cartesianProduct(iota(arr.length),iota(arr[0].length))
        .filter!(a=>arr[a[0]][a[1]]=='*')
        .each!(a=>writeln(componentSize(a.expand)));
}

(This works even if there are * at the border.)

Reply via email to