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