LeetCode-Python-200. 島の数

'1'(陸地)と'0'(水)からなる2次元メッシュを与え,島の数を計算した.1つの島は水に囲まれ、水平方向または垂直方向に隣接する陸地で接続されている.グリッドの4つのエッジが水で囲まれていると仮定できます.
例1:

  :
11110
11010
11000
00000

  : 1

例2:

  :
11000
11000
00100
00011

  : 3

第一の考え方:
DFS+visited配列は行ったポイントを保存します.

class Solution(object):
    def numIslands(self, M):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not M or not M[0]:
            return 0
        m, n = len(M), len(M[0])
        visited = [[0 for j in range(n)] for i in range(m)]
        # print visited
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]
        res = 0
        
        def dfs(x0, y0):
            for k in range(4):
                x = x0 + dx[k]
                y = y0 + dy[k]
                # print x, y
                if 0<= x < m and 0 <= y < n and M[x][y] == '1' and visited[x][y] ==0:
                    visited[x][y] = 1
                    dfs(x, y)

        for i in range(m):
            for j in range(n):
                if M[i][j] == '1' and visited[i][j] == 0:
                    res += 1
                    visited[i][j] = 1
                    dfs(i, j)
                    # print visited
                    
        return res

2つ目の考え方:
DFS+染色、スキャン入力、「1」にスキャンすると、まずそれを「0」に変え、それにつながっている点を再帰的に「0」に変え、
この問題はLeetCodeのウェブサイトの出力が自動的にu"1"になる点で、解決方法は“1”と比べないで、“1”と比べるのです.encode(「utf-8」)をマッチングします.

# -*- coding: utf-8 -*-
class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        island = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1".encode('utf-8'):
                    print i,j
                    island += 1
                    self.checkNearbyIsland(grid, i, j)
                    # print island
        return island

    def checkNearbyIsland(self, grid, i, j):
        rows = len(grid)
        columns = len(grid[0])
        print i,j
        if i > rows - 1 or j > columns - 1 or i < 0 or j < 0 or grid[i][j] == "0".encode('utf-8'):
            return 
        
        if  grid[i][j] == "1".encode('utf-8'):
            grid[i][j] = "0"
            # print grid
            self.checkNearbyIsland(grid, i + 1, j)
            self.checkNearbyIsland(grid, i, j + 1)
            self.checkNearbyIsland(grid, i - 1, j)
            self.checkNearbyIsland(grid, i, j - 1)

3つ目の考え方:
セットを使用して確認します.

# -*- coding: utf-8 -*-
class UnionFindSet(object):
    def __init__(self, grid):

        m, n = len(grid), len(grid[0])
        self.roots = [-1 for i in range(m*n)]
        self.rank = [0 for i in range(m*n)]
        self.count = 0
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    self.roots[i * n + j] = i * n + j
                    self.count += 1
        
    def find(self, member):
        tmp = []
        while member != self.roots[member]:
            tmp.append(member)
            member = self.roots[member]
        for root in tmp:
            self.roots[root] = member
        return member
        
    def union(self, p, q):
        parentP = self.find(p)
        parentQ = self.find(q)
        if parentP != parentQ:
            if self.rank[parentP] > self.rank[parentQ]:
                self.roots[parentQ] = parentP
            elif self.rank[parentP] < self.rank[parentQ]:
                self.roots[parentP] = parentQ
            else:
                self.roots[parentQ] = parentP
                self.rank[parentP] -= 1
            self.count -= 1
   
class Solution(object):
    def numIslands(self, M):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not M or not M[0]:
            return 0
        
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]
        
        ufs = UnionFindSet(M)
        m, n = len(M), len(M[0])
        
        for i in range(m):
            for j in range(n):
                if M[i][j] == '1':
                    
                    for k in range(4):
                        x = i + dx[k]
                        y = j + dy[k]
                        
                        if 0 <= x < m and 0 <= y < n and M[x][y] == '1':
                            ufs.union(i*n + j, x *n + y)
        # print ufs.roots
                            
        return ufs.count