Anzahl der Inseln in binärer Matrix (mit Umhüllung)

Ich habe diesen Python-Code, der die Anzahl der Inseln (gruppierte 1) in einer binären Matrix zählt. Wie würde ich dies ändern, um das Wrapping oben und unten zu berücksichtigen?Anzahl der Inseln in binärer Matrix (mit Umhüllung)

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)

Diese derzeit gibt eine Anzahl von 2, jedoch sollte 1 zurück, wie die rechte untere Insel sollte mit der Nummer auf der unteren linken nach der Umhüllung als Teil der größeren Insel gezählt werden.

Quelle

2017-10-03 Christopher Wong

Sie vielleicht wäre würde bedeuten, verbundenen Komponenten –

@ReblochonMasque angeschlossenen Komponenten nachschauen sollte die untere rechte eine separate Insel –

Nicht unbedingt; Es hängt von der Datenstruktur ab, die Sie verwenden. –

Ist das nicht offensichtlich? Ihre Suchfunktion muss nur umbrechen, statt anzuhalten, wenn sie auf eine Kante trifft.

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)

Dies im Hinblick auf die Modulo-Operation einfacher ausgedrückt werden kann:

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)

Quelle

2017-10-03 16:52:01 jasonharper

Ich denke, das ist eine großartige Lösung. Danke für die Veranschaulichung eines einfachen und direkten Ansatzes! –

Anzahl der Inseln in binärer Matrix (mit Umhüllung)

Antwort

Verwandte Themen