2 Number of island I

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:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

https://leetcode.com/problems/number-of-islands/

思路：这道题也是典型的套用union find就可以解的问题。代码简单到一看就懂哈。就是union的时候岛数减1就行了。

class union(object):
    def __init__(self):
        self.dic = {}
        self.sz = {}
        self.cnt = 0

    def add(self, p):
        self.dic[p] = p
        self.sz[p] = 1
        self.cnt += 1

    def find(self, p):
        if self.dic[p]!=self.dic[self.dic[p]]:
            self.dic[p] = self.dic[self.dic[p]]
        return self.dic[p]

    def unite(self, p, q):
        x = self.find(p)
        y = self.find(q)
        if x!=y:
            if self.sz[x]>self.sz[y]:
                x, y = y, x
            self.dic[x]=y
            self.sz[y] += self.sz[x]
            self.cnt -= 1

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return 0

        u = union()

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]=='1':
                    u.add((i, j))

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]=='1':
                    for dp in [(1,0),(-1,0),(0,1),(0,-1)]:
                        x, y = i+dp[0], j+dp[1]
                        if 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y]=='1':
                            u.unite((x,y), (i,j))
        return u.cnt