diff options
Diffstat (limited to 'num_islands.py')
-rw-r--r-- | num_islands.py | 59 |
1 files changed, 59 insertions, 0 deletions
diff --git a/num_islands.py b/num_islands.py new file mode 100644 index 0000000..93c2cff --- /dev/null +++ b/num_islands.py @@ -0,0 +1,59 @@ +# 200. Number of Islands + +""" +given an 'm n' 2d binary grid 'grid' which represents a map of '1's (land) +and '0's (water), return the number of islands present. an island +issurrounded by water and is formed by connected adjacent lands horizontally +or vertically. you may assume all four edges of the grid are all surrounded +by water. +""" + + +class Solution(object): + def numIslands(self, grid): + """ + :type grid: List[List[str]] + :rtype: int + """ + if not grid: + return 0 + ans = 0 + for i in range(len(grid)): + for j in range(len(grid[0])): + if grid[i][j] == "1": + self.dfs(grid, i, j) + ans += 1 + return ans + + def dfs(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 + grid[i][j] = "#" + self.dfs(grid, i + 1, j) + self.dfs(grid, i - 1, j) + self.dfs(grid, i, j + 1) + self.dfs(grid, i, j - 1) + + +if __name__ == "__main__": + obj = Solution() + print( + obj.numIslands( + grid=[ + ["1", "1", "1", "1", "0"], + ["1", "1", "0", "1", "0"], + ["1", "1", "0", "0", "0"], + ["0", "0", "0", "0", "0"], + ] + ) + ) + print( + obj.numIslands( + grid=[ + ["1", "1", "0", "0", "0"], + ["1", "1", "0", "0", "0"], + ["0", "0", "1", "0", "0"], + ["0", "0", "0", "1", "1"], + ] + ) + ) |