用于获取可能路径的 MxN 网格(矩阵)问题

我有一个 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)


繁花如伊
浏览 148回答 2
2回答

慕妹3146593

将您的网格视为无向图:顶点是具有 1 的单元格;两个顶点之间有一条边当且仅当这些顶点垂直或水平相邻问题中的“路径”表示图形中的连接组件。所以你必须计算这些组件。这可以通过深度优先搜索算法来完成。这是一个等效的leetcode 问题,在讨论部分提供了解决方案。

一只萌萌小番薯

似乎您想获得连接组件的数量(使用 4 连接)随便找的例子另请查看Connected-component_labeling&nbsp;(对于您当前的问题来说过度杀伤力,因为您不需要标记组件)
打开App,查看更多内容
随时随地看视频慕课网APP

相关分类

Python