Day 17 of 30 Day LeetCode Challenge

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

//fast I/O
static auto x = [](){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return nullptr;
}();

class Solution {
public:

pair<int, int> findNextOne(vector<vector<char>> grid){
for(int i=0;i<grid.size();++i){
for(int j=0;j<grid[i].size();++j){
if(grid[i][j]==’1') return make_pair(i, j);
}
}
return make_pair(-1, -1);
}

void bfs(vector<vector<char>>& grid, int i, int j){
int rowSize = grid.size();
int colSize = grid[0].size();

grid[i][j] = ‘v’; //visited

//bfs on all its neighbours
int r[4] = {-1, 0, 1, 0};
int c[4] = {0, 1, 0, -1};

for(int k=0;k<4;++k){
int newI = i+r[k];
int newJ = j+c[k];
if( (newI>=0&&newI<rowSize)&&(newJ>=0&&newJ<colSize)&&grid[newI][newJ]==’1') bfs(grid, newI, newJ);
}
}

int numIslands(vector<vector<char>>& grid) {

int islands = 0;

//method : O(v²) time & O(1) space
//bfs : strongly connected components
pair<int, int> index = findNextOne(grid);

while(index.first!=-1){

++islands;

//bfs starting from (index.first, index.second)
bfs(grid, index.first, index.second);


//next connected component
index = findNextOne(grid);
}

return islands;
}
};