Number of Islands

Problem: Number of Islands

This is a typical union-find problem. By union we can combine separate islands to one island, and by find we can know which island adjacent point belongs to.

In this problem, to simplify the situation, we use a list to denote different islands. By default, value of each island equals its index. When we want to union 2 islands, we just assign the same value to these 2 islands. Besides, we also do in-place reassigning to denote which island adjacent point belongs to. Thus, when we can easily do finding by access value of adjacent blocks.

Code in Python:

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        ans = []
        for i in xrange(len(grid)):
            for j in xrange(len(grid[0])):
                if grid[i][j] == '1':
                    up, left = None, None
                    if i > 0:
                        if grid[i-1][j] != '0':
                            up = grid[i-1][j]
                    if j > 0:
                        if grid[i][j-1] != '0':
                            left = grid[i][j-1]
                    if up != None and left != None and up != left:
                        # ans[left], grid[i][j] = ans[up], ans[up]
                        tmp = ans[left]
                        for k in xrange(len(ans)):
                            if ans[k] == tmp:
                                ans[k] = ans[up]
                        grid[i][j] = ans[up]
                    elif up != None and left != None and up == left:
                        grid[i][j] = ans[up]
                    elif up != None:
                        grid[i][j] = ans[up]
                    elif left != None:
                        grid[i][j] = ans[left]
                    else:
                        ans.append(len(ans))
                        grid[i][j] = ans[-1]
        ans = set(ans)
        return len(ans)