https://leetcode.com/problems/number-of-islands/description/
DFS of a map, O(N^2)
class Solution {
public:
bool visit(vector<vector<char>>& grid, int row, int col)
{
// if has any island, return true
// DFS on grid
const int rows = grid.size();
if (rows == 0 || row >= rows || row < 0)
return false;
const int cols = grid[0].size();
if (cols == 0 || col >= cols || col < 0)
return false;
if (grid[row][col] == 'V')
return false;
else if (grid[row][col] == '0')
return false;
grid[row][col] = 'V';
visit(grid, row, col-1);
visit(grid, row-1, col);
visit(grid, row+1, col);
visit(grid, row, col+1);
return true;
}
int numIslands(vector<vector<char>>& grid) {
// mark visited as 'V'
int result = 0;
for (int row = 0; row < grid.size(); ++row)
{
for (int col = 0; col < grid[0].size(); ++col)
{
if (grid[row][col] == 'V' || grid[row][col] == '0')
{
continue;
}
if (visit(grid, row, col))
result++;
}
}
return result;
}
};