美团4-4笔试第四题（Java）

/**
 * @author zhangbingbing
 * @version 1.0
 * @date 2021/4/4 11:16
小美在路上看到一些小学生在玩跳方格，她也想跟着一起玩。
这个方格被划分为n×n的小方格，即有n行n列。
每一个小方格上面都是一个1~k的正整数。小美想依次从1,2,…,k这个顺序来跳。
一开始小美可以站在任意一个小方格。
从一个方格跳到另一个方格的花费为两个方格的曼哈顿距离。
小美想知道是否可以依照该顺序一直跳到k，如果可以，最小的总花费是多少。

两个格子(x1,y1),(x2,y2)的曼哈顿距离为：|x1-x2|+|y1-y2|。
例如(3,4),(1,6)的曼哈顿距离为|3-1|+|4-6|=4。
 */
-------------------------------------------------------------------------------------------------------------------------------

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static int n;
    public static int[][] arr;
    public static int[][] dp;//保存当前格网的最小曼哈顿距离（from源点格网1）

    //递归求解指定格网的最小曼哈顿距离
    public static void dfs(int x, int y) {
        //已计算过不再计算
        if (dp[x][y] != -1) {
            return;
        }
        //到达源点格网
        if (arr[x][y] == 1) {
            dp[x][y] = 0;
            return;
        }
        int minPath = Integer.MAX_VALUE;
        int neiborValue = arr[x][y] - 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                //递归求解期望临近值的最小曼哈顿距离
                if (arr[i][j] == neiborValue) {
                    int mhdDis = Math.abs(i - x) + Math.abs(j - y);
                    dfs(i, j);
                    minPath = Math.min(minPath, dp[i][j] + mhdDis);
                }
            }
        }
        dp[x][y] = minPath;
        /*
        Bug场景再现：
        为arr赋值的过程中进行dfs，有的数字找不到，因为arr里还大都是0，上方循环后直接走到dp[x][y]=minPath
        此时将Java里的Integer.MAX_VALUE赋值给一个负数-1，该负数会变为Integer.MIN_VALUE，导致结果minPath为Integer.MIN_VALUE
         */
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int k = scanner.nextInt();
        //务必先填满数组再找路径
        arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = scanner.nextInt();
            }
        }
        int minPath = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                //从每一个k值终点格网回溯一次，创建一次dp[][]
                if (arr[i][j] == k) {
                    dp = new int[n][n];
                    for (int[] arrval : dp) {
                        Arrays.fill(arrval, -1);
                    }
                    dfs(i, j);
                    minPath = Math.min(minPath, dp[i][j]);
                }
            }
        }
        System.out.println(minPath);
    }
}