-1

大小为 N 的二进制矩阵中的“路径”是从 (0,0) 开始到 (N,N) 结束的有序单元格集合，因此路径中每个单元格的条目都是 1。

例如-> 矩阵：

1100
1100
0010
0001

有两条路径：
(0,0)->(0,1)->(1,1)->(2,2)->(3,3)和
(0,0)->(1,0)->(1,1)->(2,2)->(3,3)

打印所有可能路径的最佳方法是什么？目前，我只能想到蛮力解决方案，我一直跟随最低的'1'并将它们一个一个地设为零。

4

2 回答 2

3

将您的问题建模为图形 G=(V,E)，其中：
V = { all nodes marked as 1 }和
E = { (u,v) | u,v are in V and u,v are "neighbors" in the matrix }

查找所有路径的最简单方法是使用DFS而不维护visited集合 - 并迭代地执行此操作，直到用尽所有可能的路径。

请注意，如果图形有循环（并且您实际上想要所有简单路径，因为在带有循环的图形中可能有无限数量的路径）-那么您将需要为visited每个路径维护一个“特殊”集-该集将保留当前探索路径中的所有节点，一旦您从 DFS 中的递归调用“返回”，就会从中删除一个顶点。

请注意，路径的数量是指数的——并且您希望将它们全部打印出来——因此运行时间不能低于这个问题的指数。

于 2012-11-07T08:58:29.970 回答
1

你的问题不是很清楚。我假设可能的方向是正确的一步（例如： (1,1) -> (1,2) ），向下一步（例如：(1,1,) -> (2, 1)) 或向右和向下一步（例如：(1,1) -> (2,2)）。否则，正如 amit 所讨论的那样，可能有无数条路径。

在您的问题中，应该有三种可能的路径。正如nav_jan提到的，(0,0)->(1,1)->(2,2)->(3,3)也是一种可能的路径。

我设计了一个递归的方法，很容易理解。从 (0,0) 点开始，尝试向三个方向移动。如果当前点为 1，则继续移动，否则返回。一旦到达 (n-1,n-1) 点，就会找到一条有效路径。

代码是用 Java 编写的。

public static List<String> getMatrixPaths(int[][] matrix){
    List<String> pathList = new ArrayList<String>();
    if(matrix != null && matrix.length > 0){
        getMatrixPaths(matrix, 0,0, "", pathList);
    }
    return pathList;
}
public static void getMatrixPaths(int[][] matrix, int i, int j, String path, List<String> pathList){
    int n = matrix.length - 1;
    if(i > n || j > n){
        return;
    }else if( matrix[i][j] == 1){//only 1 is valid
        path += String.format(" (%d,%d)", i , j);
        if( i ==n && j == n){ // reach (n,n) point
            pathList.add(path);
        }else {
            getMatrixPaths(matrix, i +1, j , path, pathList);
            getMatrixPaths(matrix, i , j +1, path, pathList);
            getMatrixPaths(matrix, i + 1 , j +1, path, pathList);
        }
    }
}

使用有问题的矩阵进行测试，我的结果是 [ (0,0) (1,0) (1,1) (2,2) (3,3), (0,0) (0,1) (1 ,1) (2,2) (3,3), (0,0) (1,1) (2,2) (3,3)] 。

你可以参考这个问题：Algorithm for find all paths in a NxN grid。我认为它们非常相似。

于 2012-11-08T09:45:38.270 回答