Islands - problem

[jgg2002]

The problem goes as follows. You are given an integer N, and then N lines consisting of N integers. This represents a map, where, any land is represented by 0 and all sea by 1. An island, is considered when the 0 are horizontally or vertically connected to another piece of land.

For example the following input:
2
1 0
0 0
there is one island

and in the input:
2
0 1
1 0
there are 2 islands

bigger example:
6
1 1 1 1 1 1
1 1 1 1 0 0
1 0 0 1 1 1
1 0 1 1 1 1
1 1 1 1 0 1
1 1 1 1 1 0
there are 4

Here's my code, but one of the five test cases of the online autocompile engines returns an error for one of the test cases(don't know what it is, you can't see it)

  #include<iostream>
using namespace std;

int main(){
int n;
cin>>n;
int pin[n][n];
for(int i=0; i<n; i++){
    for (int j=0; j<n; j++){
        cin>>pin[i][j];
    }
}
int islands = 0;
for (int i=0; i<n; i++){
    for(int j=0; j<n; j++){
        if (pin[i][j]==0){
            if (pin[i][j+1]!=0 && (pin[i-1][j]!=0 || i==0)){
                islands++;
            }
        }
    }
}
cout<<islands;
}

[booradley60]

The good thing about using ints to represent land and sea is that there are plenty of ints left to use to represent other things. If 0 represents land, and 1 represents sea, what if we have 2 represent "land that's been visited already"?

We could have an algorithm that updates the map as we go over it.

1. Start with a count of islands initialized to zero (like line 13 in your code).

2. Use nested for-loops to go square by square through the whole map.

For each square on map
        if currentSquare is unvisited land
        |       mark it as visited land
        |       check each neighbor
        |       if no neighbor is visited land
        |       |       increment island counter
        |
        else
        |       do nothing for this square

[jgg2002]

Actually, every time it finds a zero, mark all connected land with 2 and increase counter by one, right?

[ne555]

3
1 0 1
0 0 0
1 1 1

your program gives 2, it should be 1.

> mark all connected land with 2
flood fill, don't just stop at the neighbours.

To avoid out of bounds access, I would suggest you to make the map bigger, (n+2 x n+2) and fill the borders with 1.

[booradley60]

Yep, my bad. A recursive approach to flood fill is probably the easiest to understand. When you find an unvisited piece of land for the first time, increment the island counter. Then invoke a recursive function to mark all the connected land as visited.

What might that recursive function look like? In this case, I perform bounds checking before looking at neighboring cells. ne555's alternative of expanding the boundaries of the map and filling the edges with SEA marks would eliminate the need for bounds checking.

// i: current row in the map
// j: current column in the map
// m: map of land and sea, expressed as ints
// N: dimension of the map
void markAllNeighboringLand(int i, int j, int** m, int N)
{
    //first check that one row up is in bounds
    //then check that the square that's one row up is LAND
    if(i-1 >= 0 && m[i-1][j] == 0)
    {
        //if so...
        m[i-1][j] = 2; //mark it as visited
        markAllNeighboringLand(i-1, j, m, N); //go do the same check on all its neighbors
    }

    //same, but for one row down
    if(i+1 < N && m[i+1][j] == 0)
    {
        m[i+1][j] = 2;
        markAllNeighboringLand(i+1, j, m, N);
    }

    //same, but for one column left
    if(j-1 >= 0 && m[i][j-1] == 0)
    {
        m[i][j-1] = 2;
        markAllNeighboringLand(i, j-1, m, N);
    }

    //same, but for one column right
    if(j+1 < N && m[i][j+1] == 0)
    {
        m[i][j+1] = 2;
        markAllNeighboringLand(i, j+1, m, N);
    }
}

[jgg2002]

@ne555 yeah, that's what I meant, mark each island you visit.