题解 | #岛屿数量#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 判断岛屿数量
# @param grid char字符型二维数组 
# @return int整型
#
dx = [1,-1,0,0]
dy = [0,0,1,-1]

class Solution:
    def __init__(self) -> None:
        self.flag = {}
        self.grid = None
        self.count = []
        self.delone = {}
        self.vis = {}

    def ok(self,x,y):
        n = self.n
        m = self.m
        if x<0 or x>n-1 or y<0 or y>m-1:
            return False
        elif (x,y) in self.vis.keys():
            return False
        else:
            return True

    def search(self,this,nowflag):
        if this in self.vis.keys():
            return 0
        val = self.grid[this[0]][this[1]]
        self.vis[this]=1
        if val=='0':
            return 0
        if this in self.flag.keys():
            thisflag = self.flag[this]
            minc = min(thisflag,nowflag)
            delc = max(thisflag,nowflag)
            self.delone[delc]=minc
            self.count.remove(delc)
            thisflag = minc
            self.flag[this]=thisflag
        else:
            self.flag[this] = nowflag
            thisflag = self.flag[this]
            if nowflag not in self.count:
                self.count.append(nowflag)
        for _ in range(4):
            x = this[0] +dx[_]
            y = this[1] +dy[_]
            if self.ok(x,y):
                back = self.search((x,y),thisflag)
        
        return 1
         
    def solve(self , grid: List[List[str]]) -> int:
        # write code here
        self.grid = grid
        self.n = len(grid)
        self.m = len(grid[0])

        nowflag = 1

        for i in range(self.n):
            for j in range(self.m):
                back = self.search((i,j),nowflag)
                if back == 1:
                    nowflag+=1

        return len(self.count)