在 0 和 1 的矩阵中查找路径

Question

最近遇到了下面的面试题？

问题： 给定一个二维矩阵，有 M 行，N columns.You 最初位于 (0,0)，即左上角数组中的单元格。您可以向右或向下移动。该数组由 1 和 0 填充。 1 表示您可以穿过该单元格，0 表示您不能穿过该单元格。 Return 从左上角单元格到右下角单元格的路径数。（即（0,0）到（M-1，N-1））。由于答案可能很大，因此您必须 return ans%(10^9+7).

任何人都可以告诉我如何处理或任何可能有帮助的算法吗？

编辑 :

I have an approach 
1.Start with the top-left cell,initialize count=0
do 
2.Check if 1 exists in adjacent right or adjacent down cell.
3.Add the tuple (i,j) in the stack and choose the right path.
4.If we reach the bottom right cell , update count and pop from stack and go to that position (i,j).
while(stack is not empty)
5.Print count

我想知道是否有人有其他方法？

Answer 1

您可以将您的问题建模为 Directed Acyclic Graph (DAG), and then you are looking for number of paths from vertex s to vertex t, which is pretty easy to do in DAG using Dynamic Programming (DP)。

在这里，将使用以下伪代码完成：

D(0,0) = 1 
D(x,y) = 0                      if x < 0
D(x,y) = 0                      if  y < 0
D(x,y) = 0                      if matrix[x][y] = 0
         D(x,y-1) + D(x-1,y)    Otherwise

通过对上述应用动态规划方法，你会得到一个矩阵，其中D(x,y)表示从(0,0)到(x,y)的路径数，你的解决方案是D(n,m).

这个解决方案的时间复杂度是O(n*m)

这个解决方案的实施留给了您，因为在理解了它是如何完成之后应该相当容易。

Answer 2

伙计们，经过我的努力，我终于提交了我的代码，它打印了从 (0,0) 开始的矩阵中的路径位置。

#!/usr/bin/env python

rows, cols = 0, 0
def traverse_matrix(A, directions, i, j, visited):
    global rows, cols
    def can_we_proceed(A, row, col, visited, current):
        return (row >=0 and row < rows and col >=0 and col < cols and \
                not visited[row][col] and (current == A[row][col]) and A[row][col] == 1)

    visited[i][j] = True
    for k in range(len(directions)):
        if can_we_proceed(A, i+directions[k][0], j+directions[k][1], visited, A[i][j]):
            print "({0},{1})".format(i+directions[k][0],j+directions[k][1])
            traverse_matrix(A, directions, i+directions[k][0], j+directions[k][1], visited)

def mysolution(a):
    global rows, cols
    rows, cols = len(a) , len(a[0])
    if (rows == 1 or cols == 1):
        return 1
    directions = [[1, 0], [0, -1], [-1, 0], [0, 1]]
    visited = []
    for i in range(rows):
        l = []
    for j in range(cols):
        l.append(False)
    visited.append(l)

    # tup1 = ();
    for i in range(rows):
        for j in range(cols):
            # tup1 = (i,j);
            if not visited[i][j]:
                traverse_matrix(A, directions, i, j, visited)   
                # print "Traversed {0};".format(tup1)

在 0 和 1 的矩阵中查找路径

Find path in a matrix of 0's and 1's

c

python

algorithm

matrix

depth-first-search