带障碍物的二维矩阵最大和路径求解及最优路径回溯问题

你已经通过DFS计算出了每个位置(i,j)到终点的最大路径和缓存数组cache，只需要从起点出发按照cache的取值反推每一步的选择即可得到最优路径，具体逻辑和实现如下：

实现思路 #

1. 你现有代码的cache[i][j]存储的是从坐标(i,j)出发到矩阵终点的最大路径和，计算逻辑是取「向下走的总路径和」和「向右走的总路径和」的最大值
2. 回溯时从起点(0,0)开始，每一步判断可选方向：
   • 如果当前已经走到最后一行，只能全部向右走
   • 如果当前已经走到最后一列，只能全部向下走
   • 如果两个方向都可通行，比较下方位置cache[i+1][j]和右方位置cache[i][j+1]的取值，选择取值更大的方向走即可（如果两者相等，任选其一都能得到最大和路径）

完整代码示例 #

首先调整你的DFS代码适配终点边界判断，然后新增路径回溯方法：

import java.util.*;

public class MaxPath {
    // 原有DFS方法，仅补充终点边界判断
    public static int dfs(char[][] matrix, int i, int j, int[][] cache) {
        // 走到终点直接返回当前点的数值
        if (i == matrix.length - 1 && j == matrix[0].length - 1) {
            if (matrix[i][j] != 'X' && matrix[i][j] != 'x' && matrix[i][j] != '.') {
                cache[i][j] = Character.getNumericValue(matrix[i][j]);
            } else {
                cache[i][j] = 0;
            }
            return cache[i][j];
        }
        if (cache[i][j] != 0) {
            return cache[i][j];
        }

        if (matrix[i][j] != 'X' && matrix[i][j] != 'x' && matrix[i][j] != '.') {
            cache[i][j] += Character.getNumericValue(matrix[i][j]);
        }
        
        int iDown = i + 1;
        int jRight = j + 1;
        int dirDown = Integer.MIN_VALUE;
        int dirRight = Integer.MIN_VALUE;

        if (iDown < matrix.length && matrix[iDown][j] != 'X' && matrix[iDown][j] != 'x') {
            dirDown = cache[i][j] + dfs(matrix, iDown, j, cache);
        }

        if (jRight < matrix[0].length && matrix[i][jRight] != 'X' && matrix[i][jRight] != 'x') {
            dirRight = cache[i][j] + dfs(matrix, i, jRight, cache);
        }

        cache[i][j] = Math.max(dirDown, dirRight);
        return cache[i][j];
    }

    // 新增回溯路径的方法
    public static String getPath(char[][] matrix, int[][] cache) {
        StringBuilder path = new StringBuilder();
        int i = 0, j = 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        while (i != rows - 1 || j != cols - 1) {
            // 已经到最后一行，只能往右走
            if (i == rows - 1) {
                path.append('R');
                j++;
            }
            // 已经到最后一列，只能往下走
            else if (j == cols - 1) {
                path.append('D');
                i++;
            }
            // 两个方向都可选
            else {
                boolean canDown = matrix[i+1][j] != 'X' && matrix[i+1][j] != 'x';
                boolean canRight = matrix[i][j+1] != 'X' && matrix[i][j+1] != 'x';
                if (canDown && (!canRight || cache[i+1][j] > cache[i][j+1])) {
                    path.append('D');
                    i++;
                } else {
                    path.append('R');
                    j++;
                }
            }
        }
        return path.toString();
    }

    public static void main(String[] args) {
        char[][] matrix = {
            ".X..X..".toCharArray(),
            "2...2..".toCharArray(),
            "..X.1..".toCharArray(),
            "2.....X".toCharArray()
        };
        // 如果终点为(3,5)而非最后一个格子，可自行调整边界判断逻辑，即可输出DRRRRRD
        int[][] cache = new int[matrix.length][matrix[0].length];
        // 先填充cache数组
        dfs(matrix, 0, 0, cache);
        // 回溯得到路径
        String path = getPath(matrix, cache);
        System.out.println(path);
    }
}

注意事项 #

如果你的矩阵中所有路径和都可能为0，需要把cache数组的初始值改为-1，避免DFS重复计算的问题，调整DFS开头的判断即可。

内容的提问来源于stack exchange，提问作者nanh