Number of Islands

http://www.1point3acres.com/bbs/thread-137243-1-1.html

题目描述

解题方法

Solution

九章的答案

class Solution:
    # @param {int} n an integer
    # @param {int} m an integer
    # @param {Pint[]} operators an array of point
    # @return {int[]} an integer array
    def __init__(self):
        self.f = []

    def find(self, x):
        if self.f[x] == x:
            return x
        self.f[x] = self.find(self.f[x])
        return self.f[x]

    def merge(self, x, y):
        if self.f[x] == -1 or self.f[y] == -1:
            return False

        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.f[x] = y
            return True
        else:
            return False

    def inside(self, x, y, n, m):
        return x >= 0 and y >=0 and x < n and y < m

    def numIslands2(self, n, m, operators):
        # Write your code here
        d = [[0,1],[0,-1],[1,0],[-1,0]]
        area = 0;
        cnt = len(operators)
        ret = []
        for i in xrange(n * m): self.f.append(-1)
        for point in operators:
            num = point.x * m + point.y;
            if (self.f[num] == -1):
                area += 1;
                self.f[num] = num

            for k in xrange(4):
                x = point.x + d[k][0];
                y = point.y + d[k][1];

                if self.inside(x, y, n, m):
                    if self.merge(x * m + y, num):
                        area -= 1

            ret.append(area);

        return ret

class UnionFind(object):
    def __init__(self, size):
        self.parent = []
        for i in range(size):
            self.parent.append(-1)

    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def connected(self, i, j):
        return self.find(i) == self.find(j)

    def union(self, i, j):
        if self.parent[i] == -1 or self.parent[j] == -1:
            return False
        p_i = self.find(i)
        p_j = self.find(j)
        if p_i != p_j:
            self.parent[p_i] = p_j
            return True
        else:
            return False


class Solution(object):

    def inside(self, x, y, n, m):
        return x >= 0 and y >= 0 and x < n and y < m

    def numIslands2(self, m, n, positions):
        """
        :type m: int
        :type n: int
        :type positions: List[List[int]]
        :rtype: List[int]
        """
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]
        area = 0
        result = []

        uf = UnionFind(m*n)

        for point in positions:
            num = point[0] * n + point[1]
            if uf.parent[num] == -1:
                area += 1
                uf.parent[num] = num
            for k in range(4):
                x = point[0] + dx[k]
                y = point[1] + dy[k]

                if self.inside(x, y, m, n):
                    if uf.union(x * n + y, num):
                        area -= 1
            result.append(area)

        return result

Reference