The OP is not clear on how to handle diagonals. If adjacent 1's on the
diagonal are considered connected, then just add 4 more calls to
erase().
The standard terms are 4-connected and 8-connected. Both come up when
working with grid graphs or pixel matrices.
On Jan 10, 9:40 pm, surender sanke <surend...@gmail.com> wrote:
> @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.
