CODEWITHSUNDEEP
c++functionmultidimensional-arraynumbers
Ivaylo Hristov
Ivaylo Hristov

Reputation: 193

How to count groups of numbers in two dimensional array?

I have field from two dimensional array in which 1 is a land and 0 is nothing. When two lands stay on the same wall are called neighbors. When a land have no neighbors is called island and when it has two or more neighbors is called continent. I have to count all the islands and continents on the field. This is how i find the islands.

int find_islands(const int array[][8]) { // Find the islands in the field.
int count = 0;
for (int i = 0; i < 8; i++)
{
    for (int x = 0; x < 8; x++)
    {
        if (array[i][x] == 1)
        {

            if (i == 0)
            {
                if (x == 0)
                {
                    if (array[i][x + 1] == 0 && array[i + 1][x] == 0)
                    {
                        count++;
                    }
                }
                else if (x == 7)
                {
                    if (array[i][x - 1] == 0 && array[i + 1][x] == 0)
                    {
                        count++;
                    }
                }
                else
                {
                    if (array[i][x + 1] == 0 && array[i][x - 1] == 0 && array[i + 1][x] == 0)
                    {
                        count++;
                    }
                }

            }

            else if (i == 7)
            {
                if (x == 0)
                {
                    if (array[i][x + 1] == 0 && array[i - 1][x] == 0)
                    {
                        count++;
                    }
                }
                else if (x == 7)
                {
                    if (array[i][x - 1] == 0 && array[i - 1][x] == 0)
                    {
                        count++;
                    }
                }
                else
                {
                    if (array[i][x + 1] == 0 && array[i][x - 1] == 0 && array[i - 1][x] == 0)
                    {
                        count++;
                    }
                }
            }

            else
            {
                if (x == 0)
                {
                    if (array[i][x + 1] == 0 && array[i + 1][x] == 0 && array[i - 1][x] == 0)
                    {
                        count++;
                    }
                }
                else if (x == 7)
                {
                    if (array[i][x - 1] == 0 && array[i + 1][x] == 0 && array[i - 1][x] == 0)
                    {
                        count++;
                    }
                }
                else
                {
                    if (array[i][x + 1] == 0 && array[i][x - 1] == 0 && array[i + 1][x] == 0 && array[i - 1][x] == 0)
                    {
                        count++;
                    }
                }

            }
        }
    }
}
return count;}

This is a sample array.

int board[8][8] = {
    {0, 1, 0, 0, 1, 1, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0},
    {1, 1, 0, 0, 1, 0, 0, 0},
    {1, 1, 0, 0, 1, 0, 0, 1},
    {0, 0, 0, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0},
    {1, 1, 1, 1, 1, 0, 0, 0},
    {1, 0, 0, 1, 1, 0, 1, 0} };

My problems is that i cant think of a way to find the continents. Thanks in advance!

Upvotes: 0

Views: 1352

Answers (1)

eesiraed
eesiraed

Reputation: 4654

The algorithm you're looking for is a flood fill. For simplicity, let's change the rules a little and count islands as continents too. Imagine we reverse the scenario, so pieces of land are now deep holes in a flat surface. What you can do to count the continents is to repeatedly pick a hole you have not seen before, and dump a bunch of water in it.

This will flood everything connected to it. When you see a place that is already flooded, you know that it's part of a continent that you have counted before, and you shouldn't count it again.

How to do this with code? Create a 2D boolean array to store whether a place is flooded or not. We can call it visited. Now, we write a function to simulate the flooding process, which takes the coordinates of a square as the position to start the flood fill.

We can use an std::queue to store the positions that we want to process next. And each time we process a square we mark it as visited then look at its adjacent squares. If an adjacent square is a piece of land and we have not visited it yet, we add it to the queue.

We can now iterate over all squares, and for each square that we see which we have not visited yet, we call our flood fill function on it, which will flood that continent and mark all pieces of land belonging to it as visited. We can then count the continents by simply having a counter to keep track of how many times we see an unvisited piece of land and start a flood fill.

Now we know the total amount of continents including continents of size 1, we can simply subtract the number of islands to get the number of continents larger than a single piece of land.

I'll leave the actual implementation as an exercise for you.

Upvotes: 1

Related Questions