CODEWITHSUNDEEP
javaarraysalgorithmgraph-algorithmtraversal
Anthony
Anthony

Reputation: 331

find all vertical traversals of a multidimensional array

If I have the following multidimensional array (of an arbitrary size):

a,b,c

d,e,f

g,h,i

And I'd like to find all possible vertical traversals (adg, adh, aeh, aeg, aei, bdg, etc), how would I go about doing that in Java?

What's making this difficult for me is the fact that the array is of an arbitrary square size (you don't know if its a 2x2 or a 3x3 or 4x4), so you can't just make N nested for loops, where N = length of multidimensional array. Any help would be great!

Edit: I am defining vertical traversals as either moving down and to the left, directly down, and down and to the right

Upvotes: 3

Views: 178

Answers (1)

shiftpsh
shiftpsh

Reputation: 1926

There are many ways to solve this problem but maybe you can go for a recursive depth-first search.

Try:

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 will move y and x to adjacent cells that is strictly below current cell, and save its contents to curr. If dfs traversed to bottom, it will print curr.

Output:

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

Upvotes: 3

Related Questions