题解 | #岛屿数量#

'''
解题思路：
最简单的一种方式就是遍历数组中的每一个值，如果是1就说明是岛屿，然后把它置为0或者其他的字符都可以，只要不是1就行，
然后再遍历他的上下左右4个位置。如果是1，说明这两个岛屿是连着的，只能算是一个岛屿，我们还要把它置为0，
然后再以它为中心遍历他的上下左右4个位置……。如果是0，就说明不是岛屿，就不在往他的上下左右4个位置遍历了
'''
#
# 判断岛屿数量
# @param grid char字符型二维数组 
# @return int整型
#

class Solution:
    def solve(self , grid ):
        # write code here

        #for i in grid:
        #    print(i)

        r = len(grid)
        c = len(grid[0])

        def bfs(i,j):
            queue = [[i,j]]                    
            while queue:                
                t = queue.pop()
                i = t[0]
                j = t[1]
                grid[i][j]='0'

                if 0<=i+1<=r-1 and 0<=j<=c-1 and grid[i+1][j]=='1':
                    queue.insert(0,[i+1,j])
                if 0<=i-1<=r-1 and 0<=j<=c-1 and grid[i-1][j]=='1':
                    queue.insert(0,[i-1,j])
                if 0<=i<=r-1 and 0<=j+1<=c-1 and grid[i][j+1]=='1':
                    queue.insert(0,[i,j+1])
                if 0<=i<=r-1 and 0<=j-1<=c-1 and grid[i][j-1]=='1':
                    queue.insert(0,[i,j-1])     

        def dfs(i,j):
            grid[i][j]='0'
            if 0<=i+1<=r-1 and 0<=j<=c-1 and grid[i+1][j]=='1':
                dfs(i+1,j)
            if 0<=i-1<=r-1 and 0<=j<=c-1 and grid[i-1][j]=='1':
                dfs(i-1,j)
            if 0<=i<=r-1 and 0<=j+1<=c-1 and grid[i][j+1]=='1':
                dfs(i,j+1)
            if 0<=i<=r-1 and 0<=j-1<=c-1 and grid[i][j-1]=='1':
                dfs(i,j-1)        

        num = 0
        for i in range(r):
            for j in range(c):
                if grid[i][j]=='1':
                    num += 1
                    dfs(i,j)
        #print('')
        #for i in grid:
        #    print(i)

        return num

#grid = [['1','1','0','0','0'],['0','1','0','1','1'],['0','0','0','1','1'],['0','0','0','0','0'],['0','0','1','1','1']]  # 3
#print(Solution().solve(grid))