Simple C++ solution - beats 99.67%, easy to understand.


  • 1
    N
    class Solution {
    public:
        void dfs(vector<vector<char>>& grid, int i, int j, int m, int n){
            if(i <0 || i >=m || j<0 || j>= n || grid[i][j] == '0' || grid[i][j] == 'x')
                return;
            grid[i][j] = 'x';
            dfs(grid, i,  j-1, m,  n);
            dfs(grid, i,  j+1, m,  n);
            dfs(grid, i+1,  j, m,  n);
            dfs(grid, i-1,  j, m,  n);
        }
        int numIslands(vector<vector<char>>& grid) {
            int m = grid.size();
            if(m<1) return 0;
            int n = grid[0].size();
            int count = 0;
            for(int i=0; i<m; i++){
                for(int j=0; j<n; j++){
                    if(grid[i][j] == '1'){
                        dfs(grid, i, j, m, n);
                        count++;
                    }
                }
            }
            return count;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.