Square Matrix Traversal grouping adjacent cells with same values

Question

Given a sample square matrix (0,1) as below:

0 1 1 0 0 0
0 0 1 0 0 1
0 0 0 1 0 1
1 0 0 0 0 1
0 1 0 0 0 1
1 0 0 1 0 0

The desire output would be the number of groups of cells which have values equal to 1. e.g. the out put for the above matrix would be:

Group #1: (0,1), (0,2), (1,2), (2,3)
Group #2: (1,5), (2,5), (3,5), (4,5)
Group #3: (3,0), (4,1), (5,0)
Group #4: (5,3)

My current algorithm is as below:

for i = 0, i < matrix.dimension, i++
   for j = 0, j < matrix.dimension, j++
       if (i,j),(i,j+1),(i,j-1),(i-1,j),(i-1,j+1),(i-1,j-1),(i+1,j),(i+1,j+1),(i+1,j-1) = 1 
           push all pairs of i, j = 1 into a group

But then I am stuck at how to separate the (2,3) and (2,5) into 2 groups as they are still within a range of (i+/-1, j+/-1) if I traverse to the cell (2,4) for example. Your help is appreciated. Thanks in advance.

Answer 1

You can visualize this matrix as a graph. So at each co-ordinate (x,y), this point is connected to 8 other points i.e

(x+1, y),(x+1,y-1),(x+1,y+1),(x,y+1),(x,y-1),(x-1,y),(x-1,y+1),(x-1,y-1).

So your point (x,y) will be connected to the above 8 points. Now you have a graph ready in front of you.

Now run DFS on this graph and you can easily find the set of co-ordinates with same values grouped together.

Hope this helps!