题解 | #迷宫问题#

调了好长时间，不知道为何定义成中等的，这玩意儿要是能一两个小时之内调通的，都是高手啊。

import java.util.*;
import java.lang.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int m = in.nextInt();
            int[][] t = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    t[i][j] = in.nextInt();
                }
            }
            Stack<String> out = new Stack<>();//存放走过的正确路径，用来最后输出
            Linju first = new Linju(0, 0, n - 1, m - 1);//定义第一个点对象，设置点坐标边界
            LinkedList<String> pres = new LinkedList<>();//记忆已经走过的路径，包含走错的
            LinkedList<Linju> lll = new LinkedList<>();//存放每个点的邻居，每前进一步清空给下个点用
            Stack<Linju> jiedian = new Stack<>();//遇到一个分叉路口，纪录当前路口的点为节点，方便走错时返回来
            out.add(first.zuobiao());
            Linju now = first;
            //若未到最后一个点，就一直走
            while (!(now.x == n - 1 && now.y == m - 1) && t[now.x][now.y] == 0) {
                pres.add(now.zuobiao());//把当前点加入记忆
                //取当前点的上下左右邻居，若没有返回null
                Linju r = now.right();
                Linju l = now.left();
                Linju d = now.down();
                Linju u = now.up();
                //判断这些邻居中哪些是下一步可以走的，存入邻居组                
                for (Linju i : new Linju[] {r, l, d, u}) {
                    if (i != null && t[i.x][i.y] == 0 && !pres.contains(i.zuobiao())) {
                        lll.add(i);
                        continue;
                    }

                }

                if(lll.size()>1){
                    jiedian.add(now);//标记分叉口的节点
                }

                if (lll.size() > 0) {//若存在可走的点，则选择一个去走
                    now = lll.get(0);
                    lll.clear();
                    out.add(now.zuobiao());

                } else if (lll.size() == 0) {//若已无路可走，返回到最近的一个分叉口重新走
                    Linju prejie = jiedian.pop();
                    int jieind = out.indexOf(prejie.zuobiao());
                    for(int i=out.size()-1;i>jieind;i--){
                        out.pop();//处理掉走错的点
                    }
                    now = prejie;
                }
            }
            //输出正确的路径
            for (String s : out) {
                System.out.println(s);
            }
        }
    }
    //将点封装成对象，用于取坐标及上下左右的邻居
    public static class Linju {
        int x = 0;
        int y = 0;
        int rb = 0;
        int cb = 0;
        Linju(int x, int y, int ri, int ci) {
            this.x = x;
            this.y = y;
            this.rb = ri;
            this.cb = ci;
        }
        String zuobiao() {
            return String.format("(%d,%d)", this.x, this.y);
        }
        Linju right() {
            if (this.y < this.cb) {
                return new Linju(this.x, this.y + 1, this.rb, this.cb);
            } else {
                return null;
            }
        }
        Linju left() {
            if (this.y > 0) {
                return new Linju(this.x, this.y - 1, this.rb, this.cb);
            } else {
                return null;
            }
        }
        Linju down() {
            if (this.x < this.rb) {
                return new Linju(this.x + 1, this.y, this.rb, this.cb);
            } else {
                return null;
            }
        }
        Linju up() {
            if (this.x > 0) {
                return new Linju(this.x - 1, this.y, this.rb, this.cb);
            } else {
                return null;
            }
        }
    }
}