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.
