@gene
in that case ur erase() should even consider diagonal elements as well,
else there would be 2 islands in example
surender
On Wed, Jan 11, 2012 at 7:19 AM, Gene <gene.ress...@gmail.com> wrote:
> 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.
>
>
--
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.
