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.
