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