It can be done with flood fill, which is a variant of DFS. This assume your matrix is actually a graph, where each cell is a node, and there is an edge between two adjacent cells.
a possible pseudocode could be:
DFS(v,visited):
if v is not set:
return []
else:
nodes = [v]
for each neighbor u of v:
if u is not in visited:
visited.add(u)
nodes.addAll(DFS(u,visited))
return nodes
If you start from some point v
, it will return t list containing all nodes connected to v
(including v
itself), and you can easily set their "value" as size(nodes)
.
The following pseudo code will mark ALL nodes with the size of their "cluster":
markAll(V): //V is the set of all cells in the matrix
visited = [] //a hash set is probably best here
while (V is not empty):
choose random v from V
visited.add(v)
nodes = DFS(v,visited)
for each u in nodes:
value(u) = size(nodes)
V = V \ nodes //set substraction
Complexity of this approach will be O(|V|) = O(n*m)
- so linear in the size of the matrix (which is n*m)