[LeetCode][python3]Day17. Number of Islands (30-Day LeetCoding Challenge)

30 days! Lets go Lets go!
N2I -2020.04.18

1. My Solution

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        res=1
        """
        for row in range(len(grid)):
            print(grid[row])
        """
        for row in range(len(grid)):
            for col in range(len(grid[row])):
                if grid[row][col]=='1':
                    res+=1
                    self.explore(grid,row,col,res)
                    """
                    print()
                    for i in range(len(grid)):
                        print(grid[i])
                    print()
                    """
        if res-1:
            return res-1
        else:
            return 0
        
    def explore(self,grid,row,col,res):
        #print("\n",row,col,"\n")
        maxrow=len(grid)
        maxcol=len(grid[row])
        stack=set()
        stack.add((row,col))
        path=set()
        while stack:
            #print(stack)
            row,col=stack.pop()
            if grid[row][col]=='1':
                grid[row][col]=res
                path.add((row,col))
                if row-1>=0 and (row-1,col) not in path:
                    stack.add((row-1,col))
                if row+1<maxrow and (row+1,col) not in path:
                    stack.add((row+1,col))
                if col-1>=0 and (row,col-1) not in path:
                    stack.add((row,col-1))
                if col+1<maxcol and (row,col+1) not in path:
                    stack.add((row,col+1))

Explanation:

You can open the comment part if you want to take a look on how the map prints. The Solution will explore an island if it found "1" in map. After every explore, all "1" in the same island will be marked as another number, so it will not be explored again.

2. A Clear Solution

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:        
        if not grid:
            return 0         
        res = 0      
        n = len(grid)
        m = len(grid[0])
        for i in range(n):
            for j in range(m):
                if grid[i][j] == "1":
                    res += 1
                    self.dfs(i,j,n,m,grid)               
        return res
       
    def dfs(self, i,j,n,m,grid):
        grid[i][j] = "0"
        for x,y in [(i+1,j),(i-1,j),(i,j-1),(i,j+1)]:
            if 0<=x<n and 0<=y<m and grid[x][y] == "1":
                self.dfs(x,y,n,m,grid)

Explanation:

Logically the same as the first solution, but it is using a recursive function instead of while loop to explore the island.