How to count groups of the same cells in a 2d array?

Question

Here's an example (black count):

input:

exit:

5 4 // 5 groups (4 squares each) 1 1 // 1 group containing 1 square 

Currently, I can't think of anything better than it hurting to iterate. Is it possible to get these groups in a recursive way? Thanks

Answer 1

Set all black squares as nodes. The connection between the black squares (if the squares are next to each other) will be the edge.

This gives you a graph .

A DFS on the chart you get all the groups. Note that DFS is recursive in nature.

Answer 2

At the beginning, each cell will be “invisible”.

I will go through the cells until you meet the “invisible” black cell. Every white cell that you get to this point

As soon as you click on the black cell, you “deploy” it in all directions, if possible (similar to “floodfilling”). You expand as much as you can, and mark all visited cells as “visited”. After you have done this, you will calculate how many black cells you have infected, and you know how big the group is. After finding the group, you proceed to the next "invisible" black cell.

Answer 3

You can use the algorithm to mark connected components with 4 connections