Guys,
You are making this way too hard. It's really a graph problem. The
nodes are the 1's and adjacent 1's are connected by undirected edges.
You must count components in the graph. So the algorithm is easy:
Find a component, erase it, repeat. Count components as you go.
What's an efficient way to do this with this special kind of graph we
have? Just erase components by erasing 1's.
So we get:
#include <stdio.h>
int a[100][100] = {
{1, 1, 0, 0},
{1, 1, 0, 0},
{0, 0, 1, 1},
};
int m = 3, n = 4;
// Erase the undirected component rooted at i,j.
void erase(int i, int j)
{
// If we're off the graph or already erased,
// there's nothing to do.
if (i < 0 || j < 0 || i >= m || j >= n || !a[i][j])
return;
// Erase!
a[i][j] = 0;
// Recursively erase the 4 neighbors.
erase(i+1, j); erase(i-1, j);
erase(i, j+1); erase(i, j-1);
}
void count_islands()
{
int i, j, n_islands = 0;
// Search for a component.
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
if (a[i][j] == 1) {
// Found one! Count and erase.
n_islands++;
erase(i, j);
}
}
}
printf("found %d islands\n", n_islands);
}
int main(void)
{
count_islands();
return 0;
}
On Jan 9, 9:06 pm, Ashish Goel <ashg...@gmail.com> wrote:
> row, col, diag all
>
> 1-1-1 is a single island :)
>
> 1 1 0 0
> 1 1 0 0
> 0 0 1 1
>
> this has only 2 islands
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
>
> On Tue, Jan 10, 2012 at 7:29 AM, Ankur Garg <ankurga...@gmail.com> wrote:
> > Can you give an example
>
> > Say matrix is
>
> > 1 1 0 0
> > 1 1 0 0
> > 0 0 1 1
>
> > Has it got 3 islands i.e 1-1 be in same row or they can be column wise
> > also i.e. 5
>
> > On Tue, Jan 10, 2012 at 7:09 AM, Ashish Goel <ashg...@gmail.com> wrote:
>
> >> there is a matrix of 1 and 0
> >> 1 is a island and 0 is water
> >> 1-1 together makes one island
> >> calculate total no of islands
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
