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