时间戳

首页 > 解决方案 > 查找多维数组的所有垂直遍历

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

问题描述

如果我有以下多维数组（任意大小）：

a,b,c

d,e,f

g,h,i

而且我想找到所有可能的垂直遍历（adg、adh、aeh、aeg、aei、bdg 等），我将如何在 Java 中做到这一点？

让我感到困难的是数组是任意正方形大小的事实（你不知道它是 a2x2还是 a3x3或4x4），所以你不能只N嵌套 for loops， where N = length of multidimensional array。任何帮助都会很棒！

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

标签： javaarraysalgorithmgraph-algorithmtraversal

解决方案

有很多方法可以解决这个问题，但也许你可以使用递归深度优先搜索。

尝试：

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

推荐阅读