aboutsummaryrefslogtreecommitdiff
path: root/num_islands.py
diff options
context:
space:
mode:
Diffstat (limited to 'num_islands.py')
-rw-r--r--num_islands.py59
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"],
+ ]
+ )
+ )