Nombre d'îles dans la matrice binaire (avec emballage)

J'ai ce code Python qui compte le nombre d'îlots (groupés 1) dans une matrice binaire. Comment est-ce que je modifierais cela pour tenir compte de l'emballage en haut et en bas?Nombre d'îles dans la matrice binaire (avec emballage)

class Solution(object): 

rowLen = None 
colLen = None 

def numIslands(self, grid): 
    """ 
    :type grid: List[List[str]] 
    :rtype: int 
    """ 

    self.rowLen = len(grid) 

    if self.rowLen == 0: 
     return 0; 

    self.colLen = len(grid[0]) 

    count = 0; 

    for row in range(self.rowLen): 
     for col in range(self.colLen): 
      if grid[row][col] == '1': 
       count += 1 
       self.search(grid, row, col) 

    return count 

def search(self, grid, row, col): 
    if (row >= 0 and col >= 0 and row < self.rowLen and col < self.colLen and grid[row][col] == '1'): 
     grid[row][col] = 0; 

     self.search(grid, row - 1, col) 
     self.search(grid, row + 1, col) 
     self.search(grid, row, col - 1) 
     self.search(grid, row, col + 1)

Cela renvoie actuellement un nombre de 2, mais devrait revenir 1 l'île en bas à droite devrait être considéré comme faisant partie de la plus grande île après emballage avec le numéro en bas à gauche.

Source

2017-10-03 Christopher Wong

Vous devriez peut-être rechercher des composants connectés –

@ReblochonMasque composants connectés signifierait l'inférieur droit serait une île séparée –

Pas nécessairement; Cela dépend de la structure de données que vous utilisez. –

N'est-ce pas évident? Votre fonction de recherche a juste besoin de s'enrouler au lieu de s'arrêter quand elle touche un bord.

def search(self, grid, row, col): 
    if row < 0: 
     row += self.rowLen 
    elif row >= self.rowlen: 
     row -= self.rowlen 
    if col < 0: 
     col += self.colLen 
    elif col >= self.colLen: 
     col -= self.colLen 
    if grid[row][col] == '1': 
     grid[row][col] = 0; 

     self.search(grid, row - 1, col) 
     self.search(grid, row + 1, col) 
     self.search(grid, row, col - 1) 
     self.search(grid, row, col + 1)

Cela peut être exprimé plus simplement en termes de l'opération modulo:

def search(self, grid, row, col): 
    row %= self.rowlen 
    col %= self.colLen 
    if grid[row][col] == '1': 
     grid[row][col] = 0; 

     self.search(grid, row - 1, col) 
     self.search(grid, row + 1, col) 
     self.search(grid, row, col - 1) 
     self.search(grid, row, col + 1)

Source

2017-10-03 16:52:01 jasonharper

Je pense que c'est une excellente solution. Merci d'illustrer une approche simple et directe! –

Nombre d'îles dans la matrice binaire (avec emballage)

Répondre

Questions connexes