0

我有一个二维布尔数组：

布尔 [][] 字段 = 新布尔[7][11]；

我想要做的是检查是否存在从字段 [0] [0] 到字段 [7] [11] 的有效“路径”。

例如，这将是从开始到结束的有效路径：0 = false，1 = true

1 1 0 0 0
0 1 0 0 0
1 1 0 0 0
1 0 0 0 0
1 1 1 1 1

我们可以用真值连接 0,0 到 4,4。

无效路径示例：

1 1 0 0 0
0 1 0 0 0
1 0 0 0 0
1 0 0 0 0
1 1 1 1 1

我们无法从 0,0 连接到 4,4。（只有垂直和水平值是有效路径，而不是对角线）

我认为解决这个问题的最好方法是递归。从 0,0 开始，检查邻居是否为“真”，如果是则继续。然后再次检查邻居。如果所有邻居都是假的，则向后移动并找到另一条路径。

解决这个问题的最佳方法是什么？

编辑 ：

这就是我到目前为止所拥有的。该算法打印出完全正确的路径，但我的返回值并不总是正确的。

谁能看到错误在哪里？

static boolean isValidPath(boolean [][] field, int i, int j, int previ, int prevj) {

        if(i >= field.length && j >= field[0].length) return true;


        if(field[i][j] == true) {

            System.out.println("Valid i: " + i + ", j: " + j);
            if(i + 1 < field.length && i + 1 != previ) isValidPath(field, i + 1, j, i, j);
            if(j + 1 < field[0].length && j + 1 != prevj) isValidPath(field, i, j + 1, i, j);
            if(i - 1 >= 0 && i - 1 != previ) isValidPath(field, i - 1, j, i, j);
            if(j - 1 >= 0 && j - 1 != prevj) isValidPath(field, i, j - 1, i, j);

            return true;

        } else return false;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        boolean[][] field = new boolean[][] { { true,  true, false, false, false}, 
                                              { false, true, false, false, false},
                                              { true,  true, false, false, false},
                                              { true, false, false, false, false}, 
                                              { true, true, true, true, true }};

        System.out.println("Is this path valid: " + isValidPath(field, 0, 0, 0, 0));
    }

这是输出：

Valid i: 0, j: 0
Valid i: 0, j: 1
Valid i: 1, j: 1
Valid i: 2, j: 1
Valid i: 2, j: 0
Valid i: 3, j: 0
Valid i: 4, j: 0
Valid i: 4, j: 1
Valid i: 4, j: 2
Valid i: 4, j: 3
Valid i: 4, j: 4
Is this path valid: true

如您所见，算法在整个数组上运行，并打印出有效路径。但是，如果我例如将 [4][4] 中的值更改为 false，结果仍然是 true。

我真的不知道在哪里返回 false 和 true。

4

3 回答 3

1

你在这里所拥有的只是一个以更非规范的方式呈现的图表。任何类型的图形搜索都可以解决您的问题。我建议您使用BFS或DFS。实际上 DFS 通常是使用递归来实现的，所以，是的，你可以使用递归来解决这个问题。

于 2013-01-18T09:55:47.340 回答
0

这是一个广为人知的编程任务，有许多现成的算法。您建议的称为深度优先搜索。我会说，使用A*或Dijkstra。

于 2013-01-18T09:54:11.947 回答
0

在我看来，它就像一个经典的 TSP 问题 ( http://en.wikipedia.org/wiki/Travelling_salesman_problem )。

递归可能是最好的方法，如下所示：

bool right_path(int x, int y)
{
// check whether you have a true neighbors 
// (you can do it by yourself I hope ;)
....
// if yes, call recursive the next one

if (right_path(x+1, y) || right_path(x, y+1))
   return true;
else
   return false;
}
于 2013-01-18T10:01:58.233 回答