leetcode200

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:
11110
11010
11000
00000

Output: 1
Example 2:

Input:
11000
11000
00100
00011

Output: 3

Idea

the template for bfs:

// T 指代任何你希望存储的类型
Queue<T> queue = new LinkedList<>();
Set<T> set = new HashSet<>();

set.add(start);
queue.offer(start);
while (!queue.isEmpty()) {
    T head = queue.poll();
    for (T neighbor : head.neighbors) {
        if (!set.contains(neighbor)) {
            set.add(neighbor);
            queue.offer(neighbor);
        }
    }
}

上述代码中：
neighbor 表示从某个点 head 出发，可以走到的下一层的节点。
set 存储已经访问过的节点（已经丢到 queue 里去过的节点）
queue 存储等待被拓展到下一层的节点
set 与 queue 是一对好基友，无时无刻都一起出现，往 queue 里新增一个节点，就要同时丢到 set 里。

The que stores the nodes of the previous level and then add the nodes of the next layer again and again til the end.
In the code below the visited matrix is the same as the set.

Code

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid or len(grid) == 0:
            return 0
        
        self.grid = grid
        self.n, self.m = len(grid), len(grid[0])
        self.visited = [[False] * self.m for _ in range(self.n)]
        
        ans = 0
        for i in range(self.n):
            for j in range(self.m):
                if grid[i][j] == '1' and not self.visited[i][j]:
                    ans += 1
                    self.visited[i][j] = True
                    self.bfs(i, j)
        return ans
    
    def bfs(self, x, y):
        dzs = zip([1, 0, -1, 0], [0, 1, 0, -1])
        que = [(x, y)]
        while que:
            h = que.pop(0)
            for dz in dzs:
                x_, y_ = h[0] + dz[0], h[1] + dz[1]
                if self.isValid(x_, y_) and not self.visited[x_][y_]:
                    self.visited[x_][y_] = True
                    que.append((x_, y_))
                    
    def isValid(self, x, y):
        if x >= 0 and x <= self.n - 1 and \
            y >= 0 and y <= self.m - 1 and \
            self.grid[x][y] == '1':
                return True
        return False