Leetcode 200 Solution

This article provides solution to leetcode question 200 (number-of-islands)
Categories:
Tags:
Access this page by simply typing in "lcs 200" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/number-of-islands

Solution

class Solution {
    int m;
    int n;
public:
    int visit(vector<vector<char>>& grid, int i, int j)
    {
        grid[i][j] = '0';



        if (i - 1 >= 0 && grid[i - 1][j] == '1')
            visit(grid, i - 1, j);



        if (i + 1 < m && grid[i + 1][j] == '1')
            visit(grid, i + 1, j);



        if (j - 1 >= 0 && grid[i][j - 1] == '1')
            visit(grid, i, j - 1);



        if (j + 1 < n && grid[i][j + 1] == '1')
            visit(grid, i, j + 1);



        return 0;
    }



    int numIslands(vector<vector<char>>& grid) {
        if (grid.size() == 0 || grid[0].size() == 0)
            return 0;



        m = grid.size();
        n = grid[0].size();
        int total = 0;



        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == '1')
                {
                    visit(grid, i, j);
                    total++;
                }
            }
        }



        return total;
    }
};