top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Given a matrix with 1s and 0s ?

+6 votes
476 views

Given a matrix with 1s and 0s, please find the number of groups of 1s. A group is defined by horizontally or vertically adjacent 1s.

posted Dec 12, 2013 by Gaurav Sharma

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

We can view this question as Find Number of connected components in a graph? in which vertices are matrix positions with one's and edges are horizontally or vertically adjacent 1s

Now our aim is to find the number of connected components
We can do this by using DFS or BFS in a graph.

answer Dec 26, 2013 by Raghu
Similar Questions
+7 votes
Find the path with least sum between two zeros in a matrix?

You have a 2D matrix. Only two ZEROs in matrix.
Find the path from 1st zero to 2nd zero with least sum.

1       6       8       9       0       3

4       9       -5      5       11      13

8       9       44      23      15      -20

7       9       7       -13     14      11      

0       16      23      31      16      7

67      5       4       23      21      19

Answer

1       6       8       9       0  ----> 3
                                         |
4       9       -5      5       11      13
                                         |
8       9       44      23      15      -20
                                         |
7 <---- 9 <---- 7 <--- -13 <--- 14 <---  11     
|
0       16      23      31      16        7

67      5       4       23      21       19
+8 votes
Convert the given string into palindrome with minimum number of appends ?

Convert the given string into palindrome with minimum number of appends(at end of the given string). O(n) algorithm will be appreciated ??

Input :=> Malayal
Output :=> Malayalam

–1 vote
Write a C program to Sort a Linked List of 0s, 1s and 2s?

Given a Singly linked list with each node containing either 0, 1 or 2. Write code to sort the list.
Input : 1 -> 1 -> 2 -> 0 -> 2 -> 0 -> 1 -> 0
Output : 0 -> 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2

+5 votes
String Path in Matrix ?

How to implement a function to check whether there is a path for a string in a matrix of characters? It moves to left, right, up and down in a matrix, and a cell for a movement. The path can start from any entry in a matrix. If a cell is occupied by a character of a string on the path, it cannot be occupied by another character again.

...