题解 | #迷宫问题#—给刘思光的答案2之动态规划~

package m6_18;

import java.util.Scanner;

public class Main {
    private static int[][] mize;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int rowlen = in.nextInt();
        int collen = in.nextInt();
        mize = new int[rowlen][collen];
        for (int i = 0; i < rowlen; i++) {
            for (int j = 0; j < collen; j++) {
                mize[i][j] = in.nextInt();
            }
        }
        int needScoreTotal = 0;
        for (int i = 0; i < rowlen; i++) {
            for (int j = 0; j < collen; j++) {
                if (mize[i][j] == 1) {
                    mize[i][j] = -1;
                } else {
                    mize[i][j] = -2;
                    needScoreTotal++;
                }
            }
        }
        int index=0;
        mize[rowlen - 1][collen - 1] = 0;
        while (index<needScoreTotal-1) {
            for (int i = 0; i < rowlen; i++) {
                for (int j = 0; j < collen; j++) {
                    if (mize[i][j] == -2) {
                        mize[i][j] = getScore(i, j);
                        if(mize[i][j]!=-2){
                            index++;
                        }
                    }
                }
            }
        }

        printWay(0, 0);

    }

    private static void printWay(int x, int y) {
        System.out.println("(" + x + "," + y + ")");
        if (mize[x][y] > 0) {
            if (x + 1 < mize.length && mize[x + 1][y] == mize[x][y] - 1) printWay(x + 1, y);
            else if (x - 1 >= 0 && mize[x - 1][y] == mize[x][y] - 1) printWay(x - 1, y);
            else if (y + 1 < mize[0].length && mize[x][y + 1] == mize[x][y] - 1) printWay(x, y + 1);
            else if (y - 1 >= 0 && mize[x][y - 1] == mize[x][y] - 1) printWay(x, y - 1);
        }
    }

    private static int getScore(int x, int y) {
        int result = -2;
        if (x + 1 < mize.length && mize[x + 1][y] != -1 && mize[x + 1][y] != -2)
            result = mize[x + 1][y] + 1;
        if (x - 1 >= 0 && mize[x - 1][y] != -1 && mize[x - 1][y] != -2)
            result = result==-2?mize[x - 1][y] + 1:result <= mize[x - 1][y] + 1 ? result : mize[x - 1][y] + 1;
        if (y + 1 < mize[0].length && mize[x][y + 1] != -1 && mize[x][y + 1] != -2)
            result = result==-2?mize[x][y + 1] + 1:result <= mize[x][y + 1] + 1 ? result : mize[x][y + 1] + 1;
        if (y - 1 >= 0 && mize[x][y - 1] != -1 && mize[x][y - 1] != -2)
            result = result==-2?mize[x][y - 1] + 1:result <= mize[x][y - 1] + 1 ? result : mize[x][y - 1] + 1;
        return result;
    }

}