我有一个 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)
慕妹3146593
一只萌萌小番薯
相关分类