# 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;

}

};