CODEWITHSUNDEEP
graph-theory
user1484638
user1484638

Reputation: 341

number of connected sets

How many connected sets are there in the following array?

1 0 0 1

0 0 1 0

0 0 1 0

1 0 0 1

"Connected set" can be defined as group of cell(s) which has 1 mentioned on it and has at least one other cell in that set with which they share the neighbor relationship. A cell with 1 in it and no surrounding neighbor having 1 in it can be considered as a set with one cell in it. Neighbors can be defined as all the cells adjacent to the given cell in 8 possible directions ( i.e N , W , E , S , NE , NW , SE , SW direction ). A cell is not a neighbor of itself.

Actually i am stuck on this and not able to understand what the definition of connected set in this question means

Upvotes: 0

Views: 996

Answers (2)

monu
monu

Reputation: 698

one approach to solve the problem is use flood fill algorithm

now check for 1 and make it 0 and now check in all directions and if they contains 1 then also make them 0 (nothing but make a recursive call in all directions)

after the entire array checking is completed how many times does we faced 1 is the answer

for example let us take

1 0 0 1

1 0 0 1

1 0 0 1

1 0 1 0

now element at 00 is 1 now make it 0 and now check for in all directions now we are having 1 at 10 position hence make it zero and again check we will get 20 and 30 positions hence make a count as 1

now move to 03 make it 0 and now check for 1 hence cell containing 1 is 13 make it zero and now move to 23 and finally to 32 and increment counter hence it is 2

and now check for each and every cell since no other cells are containing 1 hence total connected sets are 2

Upvotes: 0

stanri
stanri

Reputation: 2972

Here's an image highlighting the sets:

sets

The rules apply as follows (as far as I understand):

  • Cell must contain a 1 to be part of a set
  • If a neighboring(up, down and diagonal) cell also contains a 1, it is part of the same set.
  • A cell with 1 in it and no surrounding neighbor having 1 in it can be considered as a set with one cell in it

The third point I'm not so sure on, because the OP says "'Connected set' can be defined as group of cell(s) which has 1 mentioned on it and has at least one other cell in that set", but then also says "A cell with 1 in it and no surrounding neighbor having 1 in it can be considered as a set with one cell in it", so it's very ambiguous.

If it's the case that single-cells are not sets, and the count is instead 1 and 5 respectively.

Upvotes: 2

Related Questions