Categories
不学无术

LeetCode 200. Number of Islands

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

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.