MxN сетка (матрица) задача для получения возможных путей - PullRequest
Новая
       10

MxN сетка (матрица) задача для получения возможных путей

3 голосов
/ 12 февраля 2020

У меня есть матрица MxN (заполненная только 0 и 1, я должен «посчитать» все возможные уникальные пути. Рассмотрим следующий пример: 

grid =[[1, 1, 0, 0],
       [0, 0, 1, 0],
       [0, 0, 0, 0],
       [1, 0, 1, 1],
       [1, 1, 1, 1]]

The rules of the solution are:
1) A path can be of length 1
2) A path should contains only 1's
3) Diagonal 1's are not part of a path, they stand alone as 1 path. They can be part of a path if they have adjacent 1's.  for Eg:

    grid_example =[[1, 0],
                   [0, 1]] - This grid has 2 paths, first row 1 is one path and second-row 1 is the other path


With the above rules, the initial grid has 3 path
    a) The two 1's in row 1
    b) The single 1 in row 2
    c) The series of seven 1's in row 4 and 5

Я пытаюсь подумать алгоритма о том, как решить эту проблему, но я в тупике. Кто-нибудь знает алгоритм, который может решить эту проблему? Мне нужно написать код python для того же. Мне не нужен код. Только алгоритм.

Другие примеры включают: 

grid =[[1, 0, 0, 0, 0],
       [0, 1, 0, 0, 0],
       [0, 0, 1, 0, 0],
       [0, 0, 0, 1, 0],
       [0, 0, 0, 0, 1]]
This has 5 paths. Each 1 in the diagonal form a path, since diagonal 1's cannot be part of path

Этот ответ сработал: 

def countIslands(rows, column, grid):
    def remove(i, j):
        if 0 <= i < rows and 0 <= j < column and grid[i][j] == 1:
            grid[i][j] = 0
            for x,y in zip([i+1, i-1, i, i], [j, j, j+1, j-1]):
                remove(x,y) 
            return 1
        return 0
    return sum(remove(i, j) for i in range(rows) for j in range(column))

grid = [[1,1,0,1],[0,0,1,0],[0,0,0,0],[1,0,1,1],[1,1,1,1]]
rows = 5
column = 4
final = countIslands(rows, column, grid)
print(final)

Ответы [ 2 ]

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

Рассмотрите вашу сетку как неориентированный граф :

  • вершины - это ячейки с 1 с;
  • две вершины имеют ребро между ними, если эти вершины смежны по вертикали или горизонтали

«Путь» в вашей задаче означает связанный компонент в терминах графа. Таким образом, вы должны сосчитать эти компоненты. Это может быть сделано с помощью алгоритма поиска в глубину .

Ниже приведена эквивалентная проблема с кодом leetcode с предоставленными решениями в разделе обсуждения.

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

Похоже, вы хотите получить количество подключенных компонентов (с возможностью подключения 4)

Произвольно найденный пример

Также посмотрите Connected-component_labeling (излишне для вашей текущей проблемы, потому что вам не нужны компоненты маркировки)

...