Finding the number of islands



C++ program for finding the maximum area of an island

#include<iostream>
#include<queue>
#include<tuple>

using namespace std;

class Island {

    public:

    // Below function finds the number of islands on a grid
    int GetNumber (vector<vector<char>>& grid) {

        int rows = grid.size();
        int cols = grid[0].size();

        // Assumption is that the grid size is 300 x 300
        bool visited[301][301] = {{ false }};

        queue < tuple<int, int, int>> Q;

        // For visiting Up, Right, Down and Left
        int dx[4] = { -1, 0, 1, 0 };
        int dy[4] = { 0, 1, 0, -1 };

        int num = 0;

        // Visit all not visited cells of the grid.
        for (int r=0; r<rows; r++) {
            for (int c=0; c<cols; c++) {

                // If a non visited land is found increase the count
                if (grid[r][c] == '1' and !visited[r][c]) {
                    num++;

                    Q.push(make_tuple(r,c,num));
                    visited[r][c] = true;

                    while (!Q.empty()) {

                        tuple<int,int,int> pos = Q.front();
                        Q.pop();
                        int x = get<0>(pos);
                        int y = get<1>(pos);
                        int num_island = get<2>(pos);

                        // Visit adjacent positions ( Up, Right, Down and Left )
                        for (int i=0; i<4; i++) {
                            int newx = x + dx[i];
                            int newy = y + dy[i];

                            // Check if we are going beyond the grid.
                            if (newx >= 0 and newx < rows and
                                newy >= 0 and newy < cols) {
                                if (grid[newx][newy] == '1' and !visited[newx][newy]) {
                                    Q.push(make_tuple(newx, newy, num_island));
                                    visited[newx][newy] = 1;
                                }
                            }
                        }
                    }
                }
            }
        }
        return num;
    }
};

int main () {

    vector<vector<char>> grid = { { '1', '1', '0', '0', '0' },
                                  { '1', '1', '0', '0', '0' },
                                  { '0', '0', '1', '0', '0' },
                                  { '0', '0', '0', '1', '1' } };
    Island I;

    cout << "Number of islands : " << I.GetNumber (grid) << endl;
    return 0;
}

Output

Number of islands : 3


Copyright (c) 2019-2022, Algotree.org.
All rights reserved.