Office space

[rododin]

It's coming from a Turing's Algorithm Challenge task.

I cannot copy-paste the task definition from there, so let me try to reproduce it from my memory.

There is an office space area (in a building) consisting of space cells and walls between the cells. It's represented with a matrix (2-dimension array) of MxN elements, where 0s define walls, and 1s define the space cells. Each office may consist of many cells if there are no walls between them. E.g.

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

In the given matrix we have 3 offices defined, i.e. it can be converted to the following representation where we mark each office with appropriate letter A, B and C, and wallas are marked with dots:

  A A . . .
  A A . . .
  . . B . .
  . . . C C

So, the linked (neighbor) 1s represent the same office. The purpose of the task/algorithm is to count the number of the offices at the given space area represented with the given matrix of 0s 1s.

Thus, it's a variant of the connectivity problem where we need to connect/unite neighbor cells into sets and count the number of sets.

One more variant may propose to unite the cells into named sets like shown above in the matrix with A, B, C.

Nikolay Chebotaryov (Rod Odin), 31.01.2020

[rododin]

A simple/quickl implementation has been committed. A better/optimal is still in progress, keeping the issue opened.