java - 查找多维数组的所有垂直遍历

Question

如果我有以下多维数组(任意大小):

a,b,c

d,e,f

g,h,i

我想找到所有可能的垂直遍历(adg、adh、aeh、aeg、aei、bdg 等)，我将如何在 Java 中执行此操作？

让我感到困难的是数组的大小是任意的(你不知道它是 2x2 还是 3x3 还是 4x4)，因此您不能只为 loops 嵌套 N，其中 N = 多维数组的长度。任何帮助都会很棒!

编辑:我将垂直遍历定义为向下和向左移动、直接向下、向下和向右移动

Answer 1

有很多方法可以解决这个问题，但也许你可以使用递归 depth-first search .

尝试:

public static void main(String[] args) {
    int size = 3;

    String arr[][] = {
            {"a", "b", "c"},
            {"d", "e", "f"},
            {"g", "h", "i"}
    };

    for (int i = 0; i < size; i++) {
        dfs(arr, 0, i, size, arr[0][i]);
    }
}

static void dfs(String[][] arr, int y, int x, int size, String curr) {
    if (y == size - 1) {
        System.out.println(curr);
    } else {
        if (x > 0) {
            dfs(arr, y + 1, x - 1, size, curr + arr[y + 1][x - 1]);
        }
        dfs(arr, y + 1 , x, size, curr + arr[y + 1][x]);
        if (x < size - 1) {
            dfs(arr, y + 1, x + 1, size, curr + arr[y + 1][x + 1]);
        }
    }
}

dfs 会将 y 和 x 移动到严格低于当前单元格的相邻单元格，并将其内容保存到 curr。如果dfs遍历到底部，它会打印curr。

---

输出:

adg
adh
aeg
aeh
aei
bdg
bdh
beg
beh
bei
bfh
bfi
ceg
ceh
cei
cfh
cfi