4ms C DFS solution reusing grid to memoize visited squares


  • 5
    R
    bool visit(char **grid, int numRows, int numColumns, int x, int y) 
    {
        if ( x <0 || y < 0 || x >= numColumns || y >= numRows || grid[y][x] != '1')
            return false;
        
        grid[y][x] = 'v'; //visited
        
        visit(grid, numRows, numColumns, x + 1, y);
        visit(grid, numRows, numColumns, x - 1, y);
        visit(grid, numRows, numColumns, x, y + 1);
        visit(grid, numRows, numColumns, x, y -1);
        
        return true;
    }
    
    int numIslands(char **grid, int numRows, int numColumns) 
    {
        int total = 0;
        for (int y=0; y < numRows; y++)
            for (int x=0; x < numColumns; x++)
                total += visit(grid, numRows, numColumns, x, y) ? 1 : 0;
            
        return total;
    }

  • 1
    S
    public class Solution {
        public int numIslands(char[][] grid) {
            int count=0;
            for(int x=0;x<grid.length;x++){
            	for(int y=0;y<grid[0].length;y++){
            		if(visit(grid,x,y)) count++;
            	}
            }
            return count;
        }
        private boolean visit(char[][] grid, int x, int y){
        	if(x<0||y<0||x>=grid.length||y>=grid[0].length|| grid[x][y]!='1') return false;
        	grid[x][y]='v';
        	visit(grid, x-1,y);
        	visit(grid, x,y-1);
        	visit(grid, x+1,y);
        	visit(grid, x,y+1);
        	return true;
        }  
    }

  • 0
    C

    Nice solution, here is a Python version:

    # DFS 
    def numIslands(self, grid):
        if not grid:
            return 0
        num = 0
        row, col = len(grid), len(grid[0])
        for i in xrange(row):
            for j in xrange(col):
                if self.visit(grid, i, j):
                    num += 1
        return num
                
    def visit(self, grid, i, j):
        if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != "1":
            return False
        grid[i][j] = "0"
        self.visit(grid, i-1, j)
        self.visit(grid, i+1, j)
        self.visit(grid, i, j-1)
        self.visit(grid, i, j+1)
        return True

Log in to reply
 

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