如何DFS 2D数组记录从最左列到最右列的路径？

Question

在这里，我想使用DFS遍历从最左边的列到最右边的列的2D数组，每个元素可以转到它的右上角元素或右边元素或右下角元素。我需要记录每条可能的路径。例如，我在这里：

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));
        }
    }
}