KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
i wanted to know which algorithm should i apply here. Would a DFS do? Given a 2–d matrix. Find the total number of connected sets in that matrix. Connected set can be defined as group of cell(s) which has 1 mentioned on it and have 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. For example: 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 number of connected sets is 3 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 number of connected set is 9.
Tags (comma-separated)
Save Edits
Cancel