Участник:ArthurSamuelyan/Regions Cut By Slashes

Материал из DISCOPAL
Перейти к: навигация, поиск
class Solution(object):
    def regionsBySlashes(self, grid):
        """
        :type grid: List[str]
        :rtype: int
        """
        gridD = self.createGridDetailed(grid)
        regionsCount = self.gridDCountRegions(gridD)
        return regionsCount
 
 
    # Главный финт ушами - "растеризуем" матрицу,
    # как если бы слеши были нарисованы крупными пикселями
    def createGridDetailed(self, grid):
        gridD = []
        for str in grid:
            gridD += [[], [], []]
            for sym in str:
                if sym == '/':
                    gridD[-3] += [0, 0, 1]
                    gridD[-2] += [0, 1, 0]
                    gridD[-1] += [1, 0, 0]
 
                elif sym == '\\':
                    gridD[-3] += [1, 0, 0]
                    gridD[-2] += [0, 1, 0]
                    gridD[-1] += [0, 0, 1]
 
                else:
                    gridD[-3] += [0, 0, 0]
                    gridD[-2] += [0, 0, 0]
                    gridD[-1] += [0, 0, 0]
 
        return gridD
 
 
    # По уже "растеризованной" матрице
    # можно просто посчитать число областей
    def gridDCountRegions(self, gridD):
        regionsCount = 0
        for i in range(len(gridD)):
            for j in range(len(gridD[0])):
                if gridD[i][j] == 0:
                    regionsCount += 1
                    self.fillGridDRec02(gridD, i, j)
 
        return regionsCount
 
 
 
    # Заливает "нулевые" смежные области двойками,
    # чтобы не считать их дважды
    def fillGridDRec02(self, gridD, i, j):
        if gridD[i][j] == 0:
            gridD[i][j] = 2
            if i > 0:
                self.fillGridDRec02(gridD, i-1, j)
 
            if i < len(gridD)-1:
                self.fillGridDRec02(gridD, i+1, j)
 
            if j > 0:
                self.fillGridDRec02(gridD, i, j-1)
 
            if j < len(gridD[0])-1:
                self.fillGridDRec02(gridD, i, j+1)