Problem: Assigning a group number to elements near eachother where groups are separated from spaces

Question

We have a room divided of 6x5 possible seats, every place in the 6x5 matrix could be a seat or could be empty.

We have the Matrix with all the seats already assigned on their location, and every seat has an unique code which is the actual Column(A,B,C,D,E)Row(1,2,3,4,5,6) position.

Unique code Example could be: A1, C4, E2, ....

The request is to assign the same group to all the seats that are next to each other:

Example: enter image description here

In this example the result is marked by the red color showing 3 groups.

The groups are assigned from 1 to N where the first top left will always be the first group.

There's no limitation on what to use; Arrays, Matrix, Lists, Trees, Graphs.

I would like to know if somebody here can find an efficient algorithm to execute the exercise on any seats configuration.

Answer 1

This is a classical neighbourhood-search scenario. See BFS / DFS algorithms.

You can instantiate the graph as a simple array or a two-dimensional array and have implicit edges between each two neighbouring cells that both have a seat assigned.

For example:

std::array<std::array<std::optional<unsigned>,7>,8> matrix;

As you can see, the matrix is two columns and two rows too large. If you leave these cells as sentinels you can save a lot performance. You implement a function that identifies all neighbours of a particular cell and use that to drive your BFS / DFS. You can initialise all cells containing seats to 0 and empty cells are automatically initialised to std::nullopt.

---

If you want to be slightly lazy and you have a very dense matrix, you could conceivably also go for union find.