题解 | #迷宫问题#

import java.util.Scanner;
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int m = in.nextInt();
            int[][] nums = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    nums[i][j] = in.nextInt();
                }
            }
            migong(nums, n, m);
        }
    }

    public static void migong(int[][] nums, int n, int m) {
        Position result = null;
        Queue<Position> queue = new ArrayDeque<Position>();
        queue.offer(new Position(0, 0, null));

        while (queue.size() != 0 && result == null) {
            int length = queue.size();
            for (int i = 0; i < length; i++) {
                Position p = queue.poll();
                int x = p.x;
                int y = p.y;
                if(x==m-1 && y==n-1) {
                    result = p;
                    break;
                }
                Position pre = p.pre;

                if ((pre == null || x - 1 != pre.x)
                        && x - 1 >= 0 && nums[y][x - 1] != 1) {
                    queue.offer(new Position(x - 1, y, p));
                }

                if ((pre == null || x + 1 != pre.x)
                        && x + 1 < m && nums[y][x + 1] != 1) {
                    queue.offer(new Position(x + 1, y, p));
                }

                if ((pre == null || y - 1 != pre.y)
                        && y - 1 >= 0 && nums[y - 1][x] != 1) {
                    queue.offer(new Position(x, y - 1, p));
                }

                if ((pre == null || y + 1 != pre.y)
                        && y + 1 < n && nums[y + 1][x] != 1) {
                    queue.offer(new Position(x, y + 1, p));
                }

            }
        }

        LinkedList<Position> list = new LinkedList<Position>();
        while(result != null) {
            list.add(0, result);
            result = result.pre;
        }
        output(list);
    }

    public static void output(LinkedList<Position> path) {
        for (int i = 0; i < path.size(); i++) {
            Position p = path.get(i);
            System.out.println(String.format("(%d,%d)", p.y, p.x));
        }
    }
}

class Position {
    int x;
    int y;
    Position pre;
    public Position(int x, int y, Position pre) {
        this.x = x;
        this.y = y;
        this.pre = pre;
    }
}