二维数组中的递归

Question

我有一个二维布尔数组：

boolean [] [] field = new boolean [7] [11];

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

例如，这是从头到尾的有效路径：0 =否，1 =正确

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开始，检查邻居是否为“ true”，如果是，则继续进行。然后再次检查邻居。如果所有邻居都为假，请返回并找到另一条路径。

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

编辑：

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

谁能看到错误在哪里？

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。

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

Answer 1

这里您只是以一种非规范的方式呈现的图形。任何类型的图形搜索都可以解决您的问题。我建议您使用BFS或DFS。实际上，DFS通常是使用递归实现的，因此可以使用递归解决此问题。

Answer 2

这是一个广为人知的编程任务，有许多可用的算法。您建议将其称为depth first search。我会说，使用A*或Dijkstra。

Answer 3

它看起来像是经典的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;
}