Finding maximum are of an island



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

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

class Island {

    public:
    int FindMaxArea (vector<vector<int>>& grid) {

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

        bool visited[51][51] = {{ false }};

        int area = 0; // For tracking area of current island.
        int maxarea = 0; // For tracking max area found so far.

        queue<pair<int, int>> Q; // Stores the (row, column) of the grid

        for (int r=0; r<rows; r++) {
            for (int c=0; c<cols; c++) {

                // Every time a not visited land is found set the area to 1
                if (!visited[r][c] and grid[r][c] == 1) {
                    area = 1;
                    Q.push(make_pair(r, c));
                }

                while (!Q.empty()) {
                    pair<int, int> pos = Q.front();
                    Q.pop();
                    int xcord = pos.first;
                    int ycord = pos.second;
                    visited[xcord][ycord] = true;

                    //Visited in order [Up, Right, Down Left]
                    int dx[4] = { -1, 0, 1, 0 };
                    int dy[4] = { 0, 1, 0, -1 };

                    for (int i=0; i<4; i++) {
                        int newx = xcord + dx[i];
                        int newy = ycord + dy[i];

                        // Check if we are beyond the boundry of the grid.
                        if (newx < 0 or newx >= rows or newy < 0 or newy >= cols)
                            continue;

                        if (!visited[newx][newy] and grid[newx][newy] == 1) {
                            area += 1;
                            visited[newx][newy] = true;
                            Q.push(make_pair(newx, newy));
                        }
                    }
                }
                maxarea = max(maxarea, area);
            }
        }
        return maxarea;
    }
};

int main() {

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

   cout << "Max Area : " << I.FindMaxArea (grid) << endl;
   return 0;
}

Output

Max Area : 6


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