pylist

200. Number of Islands

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. 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.

Example 1:

Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3

Constraints:

Solution

Code Steps

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        counter = 0 # counter for inslands
        qed = set() # record ever enqueued locations
        # loop iterate thorouh all locations
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                # if it is a new island
                if (grid[i][j] == '1' # if island
                    and (i, j) not in qed): # if never entered the queue
                    counter += 1 # add one island
                    # bsf traverse to visit all locations of the current island
                    q = deque([(i, j)]) # queue for a single island
                    while q: # if queue not empty
                        node = q.popleft() # current location
                        neis = self.get_neis(grid, node) # get all neighbors
                        for n in neis: # iterate through
                            if n not in qed: # if never enqueued
                                q.append(n) # enqueue
                                qed.add(n) # record enqueue
        return counter
    
    def get_neis(self, grid, node):
        alter = [
            (1, 0),
            (0, 1),
            (-1, 0),
            (0, -1),
        ] # 4 directions
        out = [
            tuple(a[i] + node[i] for i in range(2)) # two axes
            for a in alter 
        ] # 4 directions from the node
        out = [
            n for n in out
            if 0 <= n[0] < len(grid) 
            and 0 <= n[1] < len(grid[0]) # if in the grid
            and grid[n[0]][n[1]] == '1' # if is island
        ] # all possible neighbors
        return out

思路

Python 要点

1, 2
5
8
12
3, 21
6, 7
9
4
10
11
13
14
15
16, 17
23
18
19, 20
24, 25, 26, 27, 28, 29
30, 33
32
31
34, 35, 39
36, 37
38
40 

Arcived Solution

from collections import deque
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if len(grid) == 0 or len(grid[0]) == 0 :
            return 0
        
        count = 0
        visited = set()
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '0' or (i, j) in visited:
                    continue
                    
                count += 1 # number of bfs iteration(s)
                q = deque([(i, j)])
                while len(q) > 0:
                    node = q.popleft()
                    neighbors = self.find_neighbors(node, grid)
                    for nei in neighbors:
                        if grid[nei[0]][nei[1]] == '1' and nei not in visited:
                            q.append(nei)
                            visited.add(nei)
        return count
    
    def find_neighbors(self, node, grid):
        neighbors = []
        alter = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        for a in alter:
            x = node[0] + a[0]
            y = node[1] + a[1]
            if self.in_grid((x, y), grid):
                neighbors.append((x, y))
        return neighbors
    
    def in_grid(self, node, grid):
        if node[0] < 0 or node[0] >= len(grid):
            return False
        if node[1] < 0 or node[1] >= len(grid[0]):
            return False
        return True

Care