Simple c++ dfs solution


  • 0
    P
    class Solution {
    public:
        int numIslands(vector<vector<char>> &grid) {
            int m = grid.size();
            if (m==0) 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') {
                        helper(grid,i,j,m,n);
                        count++;
                    }
                }
            }
            return count;
        }
        
        void helper(vector<vector<char> >& a, int i, int j, int m, int n) {
            a[i][j] = 0;
            if (i > 0 && a[i-1][j]=='1') helper(a,i-1,j,m,n);
            if (j > 0 && a[i][j-1]=='1') helper(a,i,j-1,m,n);
            if (i < m-1 && a[i+1][j]=='1') helper(a,i+1,j,m,n);
            if (j < n-1 && a[i][j+1]=='1') helper(a,i,j+1,m,n);
        }
    };

  • 0
    Q

    Here is python version with similar thought:

    def destroy_island(self, grid, visited, i, j, h, w):
        # burn current spot
        visited.add((i, j))
        # burn to four directions
        if i-1 >= 0 and grid[i - 1][j] == "1" and (i - 1, j) not in visited: self.destroy_island(grid, visited, i - 1, j, h, w)
        if j-1 >= 0 and grid[i][j - 1] == "1" and (i, j - 1) not in visited: self.destroy_island(grid, visited, i, j - 1, h, w)
        if i+1 < h and grid[i + 1][j] == "1" and (i + 1, j) not in visited: self.destroy_island(grid, visited, i + 1, j, h, w)
        if j+1 < w and grid[i][j + 1] == "1" and (i, j + 1) not in visited: self.destroy_island(grid, visited, i, j + 1, h, w)
    
    def numIslands(self, grid):
        if not grid: return 0
        visited = set()
        counter = 0
        n = len(grid)
        m = len(grid[0])
        for i in xrange(n):
            for j in xrange(m):
                if grid[i][j] == "1" and (i, j) not in visited:
                    counter += 1
                    self.destroy_island(grid, visited, i, j, n, m)
        
        return counter
    

  • 0
    P

    you dont have to use visited. just mark the position with "0" so that you wont see it again in your search


  • 0
    Q

    The input for python are array of strings, so you need additional memory either ways

    http://stackoverflow.com/questions/8680080/why-are-python-strings-immutable-best-practices-for-using-them


  • 0
    P

    ok, good to know. :)


Log in to reply
 

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