题解 | #迷宫问题#

//回溯算法基础上简化参数
import java.util.Scanner;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.List;
import java.util.Iterator;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    while (in.hasNextInt()) {
        int r = in.nextInt();
        int c = in.nextInt();
        int[][] a=new int[r][c];
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                a[i][j]=in.nextInt();
            }
        }
        LinkedList<String> v=new LinkedList();
        //第一步默认走起点
        v.add("(0,0)");
        if(back(a,v)){
            Iterator i=v.iterator();
            while(i.hasNext()){
                System.out.println(i.next());
            }
        }
    }

}
public static boolean back(int[][] a,LinkedList<String> v) {
    int r=0,c=0;
    
    String[] end=null;
    if(v.size()>0){
        end=v.getLast().substring(1,4).split(",");
        //已选择的最后一个路径下
        r=Integer.parseInt(end[0]);
        c=Integer.parseInt(end[1]);
        //判断是否已到终点
        if(a.length-1==r&&a[0].length-1==c){
            return true;
        }
    }
    //根据最后一个选择路径动态生成选择列表
    List<String> list=new ArrayList<>();
    String node="(r,c)";
        //向上
        if(0<=r-1&&a[r-1][c]==0){
            list.add(node.replace("r",""+(r-1)).replace("c",end[1]));
        }
        //向下
        if(r+1<a.length&&a[r+1][c]==0){
            list.add(node.replace("r",""+(r+1)).replace("c",end[1]));
        }
        //向左
        if(0<=c-1&&a[r][c-1]==0){
            list.add(node.replace("r",end[0]).replace("c",c-1+""));
        }
        //向右
        if(c+1<a[0].length&&a[r][c+1]==0){
            list.add(node.replace("r",end[0]).replace("c",c+1+""));
        }
    for(int i=0,n=list.size();i<n;i++){
        node=list.get(i);
        //避免走回头路
        if(v.contains(node)){
            continue;
        }
        //选择
        v.add(node);
        //下一层决策
        if(back(a, v)){
            return true;//只有唯一解，找到解就停止
        }
       //撤销选择
        v.removeLast();
    }
    return false;
}

}