@Umer : will fail for this case :-
0 0 0 0
0 1 0 1
1 1 1 1
island = 1;
it seem your code will print island =1 ;
On Sun, Jan 15, 2012 at 3:45 PM, Umer Farooq <the.um...@gmail.com> wrote:
> Here is my solution. Please have a look at it. Any kind of positive
> criticism will be highly appreciated.
>
> bool isConnected(int **space, int x, int y)
> {
> if (x == 0 && y == 0)
> {
> return false;
> }
> if (y > 0)
> {
> if (space[x][y-1] == 1)
> return true;
> }
> if (x > 0)
> {
> if (space[x-1][y] == 1)
> return true;
> }
> if (x > 0 && y > 0)
> {
> if (space[x-1][y-1] == 1)
> return true;
> }
> if ((x-1 >= 0)&&(y+1 < sizeof(space)/sizeof(space[0][0])))
> {
> if (space[x-1][y+1] == 1)
> return true;
> }
> return false;
> }
>
> int _tmain(int argc, _TCHAR* argv[])
> {
> int len = 4;
> int breadth = 4;
> int **space;
> space = new int*[len];
> for (int i = 0; i < len; i++)
> space[i] = new int[breadth];
>
> space[0][0] = 1;
> space[0][1] = 1;
> space[0][2] = 0;
> space[0][3] = 0;
>
> space[1][0] = 1;
> space[1][1] = 1;
> space[1][2] = 0;
> space[1][3] = 0;
>
> space[2][0] = 0;
> space[2][1] = 0;
> space[2][2] = 0;
> space[2][3] = 0;
>
> space[3][0] = 0;
> space[3][1] = 0;
> space[3][2] = 1;
> space[3][3] = 1;
> int islands = 0;
> for (int i = 0; i < len; i++)
> {
> for (int j = 0; j < breadth; j++)
> if (isConnected(space, i, j) == false && space[i][j] == 1)
> islands++;
> }
>
> cout << islands<<endl;
> int r = 0;
> cin >> r;
>
> return 0;
> }
>
> The function isConnected tells if an element at x,y on matrix (space) is
> connected to an existing island or is it completely a new island.
> The 2D array used in main function is only a test case. You can replace it
> with anything you want. The nested loop in the main method iterates over
> the whole array and gets the total number of islands that are present.
>
> Anyway, nice question. I liked solving it :)
>
> One more thing. Was it asked in phone interview or on-site interview?
>
> On Wed, Jan 11, 2012 at 6:08 PM, Gene <gene.ress...@gmail.com> wrote:
>
>> 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.
>>
>>
>
>
> --
> 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.
