Part of the problem must be rules that specify how 1's can be
connected to form an island.
>From the discussion, it looks like the rules are that a 1 must be
connected North, West, East, or South. This is called a 4-connected
grid.
Another possibility would be an 8-connected grid. This is probably
what you have in mind. In this case a 1 can be connected to another 1
North, Northeast, East, Southeast, South, Southwest, West, or
NorthWest. In the code I gave in a previous message, you'd just add 4
more erase() calls for the diagonal corners.
Since the OP never said which rule to use, you are not wrong. You're
just answering a different question than he/she had in mind. This is
a difficulty that often occurs when a question is asked imprecisely.
An excellent lesson to learn for anyone who wants to be a software
engineer...
On Jan 11, 1:28 am, Umer Farooq <the.um...@gmail.com> wrote:
> I still don't get how are they two islands. As long as I have understood,
> diagonals abridge the two islands into one. In this case, these two islands
> are connected so they form one single island?
>
> 1 1 0 0
> 1 1 0 0
> 0 0 1 1
>
> This can be either one single island. Or they are three island if a change
> in direction makes a whole new island.
>
> Can anyone please clear me the problem?
>
>
>
>
>
>
>
>
>
> On Wed, Jan 11, 2012 at 10:24 AM, prakash y <yprakash....@gmail.com> wrote:
> > I think atul/Ramakanth's approach will work fine, if we include one more
> > condition
>
> > for each arr[i][j]
> > if(arr[i][j]==1)
> > {
> > if (arr[i-1][j]==0 && arr[i][j-1]==0 && arr[i-1][j-1]==0)
> > count++;
>
> > else if (arr[i-1][j]==1 && arr[i][j-1]==1 && arr[i-1][j-1]==0)
> > count--;
> > }
>
> > On Wed, Jan 11, 2012 at 8:10 AM, 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.
>
> > --
> > 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.
>
> --
> Umer
--
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.
