题解 | #迷宫问题#

/**
 * 广度优先搜索（BFS）
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer route = new StringBuffer();
        String a;
        int[] lines = new int[2];
        int[][] matrix;
        int i = 0, m, n, step = 0;
        try {
            a = r.readLine();
            char[] dim = a.toCharArray();
            splits(lines, dim);//获得矩阵行数和列数
            m = lines[0];
            n = lines[1];
            matrix = new int[m][n];
            while ((a = r.readLine()) != null && !a.isEmpty()) {
                splits(matrix[i++], a.toCharArray());//将输入数据存入矩阵
            }
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        int[][] ans = new int[m * n][2];
        i = 0;
        if (trace(matrix, ans, 0, 0, step)) {
            while (ans[i][0] != m - 1 || ans[i][1] != n - 1) {//表示已到达右下角
                a = "(" + ans[i][0] + "," + ans[i][1] + ")\n";
                route.append(a);
                i++;
            }
            a = "(" + ans[i][0] + "," + ans[i][1] + ")\n";
            route.append(a);
            System.out.print(route);
        }
    }

    //按空格分割字符串
    public static void splits(int[] arr, char[] chs) {
        int i = 0, j = 0, k = 0, l = chs.length, n = 0;
        while (i < l) {
            if (chs[i] == ' ') {
                if (k > 0) arr[j++] = n;
                n = 0;
                i++;
                continue;
            }
            k++;
            n *= 10;
            n += chs[i] - '0';
            if (i == l - 1) arr[j] = n;
            i++;
        }
    }

    //多线程编程时，静态变量的访问容易出现锁死
    public static boolean trace(int[][] matrix, int[][] ans, int i, int j,
                                int step) {
        ans[step][0] = i;//先将该步(迷宫矩阵下标索引)存入路径
        ans[step][1] = j;//先将该步(迷宫矩阵下标索引)存入路径
        step++;//步数递增
        int row = matrix.length - 1;
        int col = matrix[0].length - 1;
        if (i == row &&
                j == col) return true;//到达终点右下角，输出路径，返回true
        matrix[i][j] =
            1;//迷宫没有到达右下角，继续走下去，并且已走过的该位设为1，避免重复往回走
        if (j > 0 && matrix[i][j - 1] == 0 &&
                trace(matrix, ans, i, j - 1, step)) return true;//向左走
        if (j < col && matrix[i][j + 1] == 0 &&
                trace(matrix, ans, i, j + 1, step)) return true;//向右走
        if (i > 0 && matrix[i - 1][j] == 0 &&
                trace(matrix, ans, i - 1, j, step)) return true; //向上走
        if (i < row && matrix[i + 1][j] == 0 &&
                trace(matrix, ans, i + 1, j, step)) return true; //向下走
        matrix[i][j] = 0;//不行就重新将迷宫走过的该位置置为0
        return false;//返回false，表示该方案不行
    }
}