バイナリマトリックスの島の数（ラッピングあり）

Question

バイナリマトリックスの島の数（グループ化された1の数）を数えるこのPythonコードを持っています。どのように私は上と下にラッピングのアカウントにこれを変更するだろうか？

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) 

これは、現在、2のカウント値を返すが、右下の島は、左下の数字で包装した後、より大きな島の一部としてカウントされるべきである1を返すべきです。

11110 
11010 
11000 
10001 

Answer 1

これは明白ではありませんか？検索機能は、エッジに当たったときに停止するのではなく、ラップアラウンドする必要があります。

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) 

これはモジュロ演算の面で、より簡単に表現することができます。

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)