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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]>
>> 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 <[email protected]>
>> 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
