@Umer : it has 1 island.... ashish made editing mistake before.
On Wed, Jan 11, 2012 at 11:58 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.
>
--
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.
