-2

There is a two-dimensional matrix, elements only 0 and 1; element 1 of the upper and lower left and right elements of 1, can be defined as neighbors; as many neighbors as a group, ask how many groups of the matrix?

example

If you have idea about this question, I would like to your answer with java language.

meowgoesthedog
  • 14,670
  • 4
  • 27
  • 40
BinLee
  • 39
  • 4
  • 1
    Look up *depth-first search*. – meowgoesthedog Aug 29 '17 at 12:20
  • 1
    I see only 3 blocks in the example, considering upper and lower left are neighbors. Also, nobody here will give you an answer to your homework. Take a look at connected component algorithms, bfs, and dfs https://en.wikipedia.org/wiki/Connected_component_(graph_theory) – Logar Aug 29 '17 at 12:21
  • 1
    @Logar I believe OP means areas which are connected only by one vertical or horizontal movement; i.e. the 1 near the bottom right is in its own group. – meowgoesthedog Aug 29 '17 at 12:23
  • yup that would make sense. Thanks - Oops, misread your comment. If there is also vertical movements, the upper and lower left are one group, +2 separate groups in the bottom right. What am I missing ? – Logar Aug 29 '17 at 12:24
  • @Logar by that I mean from any element inside the group you can reach an adjacent element with only one *either* vertical *or* horizontal movement – meowgoesthedog Aug 29 '17 at 12:34
  • @meowgoesthedog So, {0, 0} and {0, 5} are connected right ? Meh, I give it up, can't see the 4th group – Logar Aug 29 '17 at 12:37
  • What have you tried so far? Show us your code! – MrSmith42 Aug 29 '17 at 13:29

1 Answers1

0

The problem is a variant of standard 'Counting no.of Connected Components' in undirected graph. You can find clear explanation and implementation of this problem as finding no of islands - here.

arunk2
  • 2,246
  • 3
  • 23
  • 35