@asimonv

Leetcode 200

How to count islands on a grid
Andre Simon

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.


Source
python
1class Solution(object):
2  # The idea is if we found a 1, means that we found an island
3  # so we have to paint every part of it. That DFS will end when
4  # we're surrounded by water, so we must find another island or 1
5  # in the matrix.
6  def numIslands(self, grid):
7      """
8      :type grid: List[List[str]]
9      :rtype: int
10      """
11      res = 0
12      for i in range(len(grid)):
13          for j in range(len(grid[0])):
14            if grid[i][j] == "1":
15                    res += 1
16                    self.dfs(i,j,grid)
17      return res
18    
19  def dfs(self, i, j, grid):
20      if i < 0 or j < 0 or i > len(grid) or j > len(grid[0]) or grid[i][j] != "1": return
21      grid[i][j] = "#"
22      self.dfs(i-1, j, grid)
23      self.dfs(i+1, j, grid)
24      self.dfs(i, j-1, grid)
25      self.dfs(i, j+1, grid)