题解 | #求最短通路值#

import java.util.*;

public class Main {

    public static int minPathValue(int[][] m) {
        if (m == null || m.length == 0 || m[0].length == 0 || m[0][0] != 1
                || m[m.length - 1][m[0].length - 1] != 1) {
            return -1;
        }
        int res = -1;
        int[][] map = new int[m.length][m[0].length];
        map[0][0] = 1;
        Queue<Integer> rQ = new LinkedList<Integer>();
        Queue<Integer> cQ = new LinkedList<Integer>();
        rQ.add(0);
        cQ.add(0);
        int r = 0;
        int c = 0;
        while (!rQ.isEmpty()) {
            r = rQ.poll();
            c = cQ.poll();
            if (r == m.length - 1 && c == m[0].length - 1) {
                return map[r][c];
            }
            WalkTo(map[r][c], r - 1, c, m, map, rQ, cQ);    //上
            WalkTo(map[r][c], r + 1, c, m, map, rQ, cQ);     //下
            WalkTo(map[r][c], r, c - 1, m, map, rQ, cQ);     //左
            WalkTo(map[r][c], r, c + 1, m, map, rQ, cQ);     //右
        }
        return res;


    }

    public static void WalkTo(int pre, int toR, int toC, int[][] m,
                              int[][] map, Queue<Integer> rQ, Queue<Integer> cQ) {
        if (toR < 0 || toR == m.length || toC < 0 || toC == m[0].length
                || m[toR][toC] != 1 || map[toR][toC] != 0) {
            return;
        }
        map[toR][toC] = pre + 1;
        rQ.add(toR);
        cQ.add(toC);
    }

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        String[] str1=in.nextLine().split(" ");
        int n=Integer.parseInt(str1[0]);
        int m=Integer.parseInt(str1[1]);
        int[][] mat=new int[n][m];
        for (int i = 0; i <n ; i++) {
            String str=in.nextLine();
            for (int j = 0; j <m ; j++) {
                mat[i][j]=str.charAt(j)-'0';
            }
        }
        int res=minPathValue(mat);
        System.out.println(res);
    }
}