Найти размер самого большого «острова» в двоичной доске с доской, представленной в виде битовой строки - PullRequest
Новая
       66

Найти размер самого большого «острова» в двоичной доске с доской, представленной в виде битовой строки

0 голосов
/ 09 февраля 2020

Я пытаюсь найти размер самого большого острова, где остров - это группа соединенных единиц, в доске n на m, представленной битовой строкой. Например, если n = m = 3 и битовая строка равна 184, это будет 010111000 в двоичном виде, поэтому плата выглядит так: 

0 1 0
1 1 1
0 0 0

То, что я пытаюсь сделать здесь, - это найти длину самый большой остров. На острове два квадрата соединены, если они имеют общий край (диагонали не учитываются). В приведенном выше примере длина самого большого острова была бы 4. Прямо сейчас, у меня это работает, если доска представлена ​​в виде массива длины m * n с каждым элементом, равным 0 или 1. Код для этого ниже (Я изменил код python из этого сайта ) 

def DFS(M, index, visited, count): 
    row, col = divmod(index, COL)
    visited[index] = True

    #checks up
    if row-1 >= 0 and M[index-COL] and not visited[index-COL]:
        count[0] += 1
        DFS(M, index-COL, visited, count)

    #checks down
    if row+1 < ROW and M[index+COL] and not visited[index+COL]:
        count[0] += 1
        DFS(M, index+COL, visited, count)

    #checks to the left
    if col-1 >= 0 and M[index-1] and not visited[index-1]:
        count[0] += 1
        DFS(M, index-1, visited, count)

    #checks to the right
    if col+1 < COL and M[index+1] and not visited[index+1]:
        count[0] += 1
        DFS(M, index+1, visited, count)

def largestRegion(M): 
    global ROW, COL
    # Make a bool array to mark visited cells.  
    # Initially all cells are unvisited  
    visited = [0] * (ROW*COL)

    # Initialize result as 0 and travese  
    # through the all cells of given matrix  
    result = 0
    for index in range(ROW*COL):

            # If a cell with value 1 is not visited
            if (M[index] and not visited[index]): 
                count = [1]  
                DFS(M, index, visited, count)  

                result = max(result , count[0]) 
    return result

M будет массивом [0,1,0,1,1,1,0,0,0], ROW = 3 и COL = 3. Поскольку я думаю, что эффективность, если это можно улучшить, используя битовую строку и битовые операции, мне было интересно, как это сделать. Любая помощь приветствуется.

...