Как DFS 2D-массив для записи путей от крайнего левого столбца до крайнего правого столбца?

Question

Здесь я хочу использовать DFS для перемещения в двумерном массиве от крайнего левого столбца к крайнему правому столбцу, каждый элемент может перейти к своему верхнему правому элементу или правому элементу или нижнему правому элементу. Мне нужно записать каждый возможный путь. Например, здесь у меня есть:

1 2 3
4 5 6
7 8 9

Тогда возможными путями будут 123, 126, 153, 156, 159, 423, 426, 453, 456, 459, 486, 489, 753, 756, 759, 786, 789

Теперь моя идея проста:

public int findSolution(int[][] array) {
        List<List<Integer>> availablePaths = new ArrayList<List<Integer>>();
        for (int i = 0; i < array.length; i++) {
            List<Integer> tempList = new ArrayList<Integer>();
            dfs(array, availablePaths, tempList, 0, i);
        }
        int res = 0;
        int min = Integer.MAX_VALUE;
        for (List<Integer> path : availablePaths) {
            min = Integer.MAX_VALUE;
            for (Integer cur : path) {
                if (cur < min) {
                    min = cur;
                }
            }
            if (min > res) {
                res = min;
            }
        }
        return res;
    }

    public void dfs(int[][] array, List<List<Integer>> availablePaths, List<Integer> tempList, int curCol, int curRow) {
        if (tempList.size() == array[0].length) {
            availablePaths.add(new ArrayList<Integer>(tempList));
            return;
        }
        tempList.add(array[curRow][curCol]);
        int startRow;
        int endRow;
        // Next Column
        if (curRow == 0) {
            startRow = 0;
            endRow = curRow+1;
        } else if (curRow == array.length-1) {
            startRow = curRow - 1;
            endRow = curRow;
        } else {
            startRow = curRow - 1;
            endRow = curRow + 1;
        }
        for (int i = startRow; i <= endRow; i++) {
            dfs(array, availablePaths, tempList, curCol + 1, i);
            tempList.remove(tempList.size()-1);
        }
    }

Однако, это не может работать из-за ArrayIndexOutOfBoundsException, поэтому я думаю, что мой код имеет неверное представление.

Может ли кто-нибудь дать решение для решения этой проблемы?

Answer 1

Следующая реализация DFS решает вашу проблему. Я добавил ваш пример в качестве контрольного примера. В основном, мы запускаем новые dfs в каждой ячейке первого столбца. В каждом вызове dfs, пока текущая ячейка находится в привязке, мы добавляем ее к текущему пути в списке. Если текущая ячейка уже является последним столбцом, добавьте путь, сохраненный в списке, к окончательному результату.

Массивы dx, dy - это краткий способ реализовать 3 возможных хода.

import java.util.ArrayList;
import java.util.List;

public class Solution {
    private static int[] dx = {-1,0,1}, dy = {1,1,1};
    public static List<List<Integer>> dfsForAllPaths(int[][] grid) {
        List<List<Integer>> res = new ArrayList<>();
        if(grid == null) {
            return res;
        }
        for(int i = 0; i < grid[0].length; i++) {
            dfsHelper(grid, i, 0, res, new ArrayList<>());
        }
        return res;
    }

    private static void dfsHelper(int[][] grid, int x, int y, List<List<Integer>> res, List<Integer> list) {
        if(!isInBound(grid, x, y)) {
            return;
        }
        list.add(grid[x][y]);
        if(y == grid[0].length - 1) {
            res.add(new ArrayList<>(list));
        }
        for(int dir = 0; dir < 3; dir++) {
            int newX = x + dx[dir], newY = y + dy[dir];
            dfsHelper(grid, newX, newY, res, list);
        }
        list.remove(list.size() - 1);
    }

    private static boolean isInBound(int[][] grid, int x, int y) {
        return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
    }
    public static void main(String[] args) {
        int[][] grid = {{1,2,3},{4,5,6},{7,8,9}};
        List<List<Integer>> res = dfsForAllPaths(grid);
        for(int i = 0; i < res.size(); i++) {
            System.out.println(res.get(i));
        }
    }
}