1、前言

2、思路

此题比较简单的思路是，针对每一个0点求到1的最短路径，使用 bfs 求解，然后找出其中最短距离的最大距离。因为 bfs 的时间复杂度为 O(n^2)，外层双层 for 循环的时间复杂度也是 O(n^2)，所以总的时间复杂度为 O(n^4)。

所以可以使用多源 bfs，首先将1先加入队列，后续在遍历0，直到所有的东西都结束。

3、代码

class Solution {
    public int minPathSum(int[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0){
            return 0;
        }

        int m = grid.length, n = grid[0].length;
        int[][] memo = new int[m][n];
        for(int[] arr : memo){
            Arrays.fill(arr, -1);
        }

        return dfs(grid, 0, 0, memo);
    }

    private int dfs(int[][] grid, int i, int j, int[][] memo){
        if(i >= grid.length || j >= grid[0].length){
            return Integer.MAX_VALUE;
        }

        if(i == grid.length - 1 && j == grid[0].length - 1){
            return grid[grid.length - 1][grid[0].length - 1];
        }

        if(memo[i][j] != -1){
            return memo[i][j];
        }

        int min = Math.min(dfs(grid, i + 1, j, memo), dfs(grid, i, j + 1, memo)) + grid[i][j];
        memo[i][j] = min;

        return min;
    }
}