java - 如何对二维数组进行 DFS 以记录从最左列到最右列的路径？

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