题解 | #迷宫问题#

Java
使用了回溯的方法
（组合问题、切割问题、子集问题、排列问题、棋盘问题都可用回溯）
一般情况下的回溯模板：

void backtracking(参数）{
    if(终止条件){
        收集结果（比如放入最大的List中）;
        return;
    }
    for(集合元素集（所有子节点个数）){
        处理节点；（加入List,连接字符串等操作）
        递归函数；
        回溯操作；（撤销节点操作）
    }
}

迷宫问题

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

//迷宫问题
public class Main {
     static List<List<Integer>> lists=new ArrayList<List<Integer>>();
     public static void main(String[] args){
         Scanner sc=new Scanner(System.in);
         while (sc.hasNext()){
            int x=sc.nextInt();
            int y=sc.nextInt();
            int[][] maze=new int[x][y];
            for(int i=0;i<x;i++){
                for(int j=0;j<y;j++){
                    maze[i][j]=sc.nextInt();
                }
            }

            List<Integer> list=new ArrayList<>();
            //创建一个新数组，用于放判断的值
            int[][] hp=new int[x][y];

            backtracking(maze,0,0,x,y,list,hp);
            //题目中说找最短路径，就拿出lists中最短的list吧。对lists按长度排序
            Collections.sort(lists, new Comparator<List<Integer>>() {
                  public int compare(List<Integer> o1, List<Integer> o2) {
                      return o1.size()-o2.size();
                  }
              });//对lists的元素按照路径长度由小到大进行排序
              list=lists.get(0);//拿出第一条路径（最短路径）
              for (int i = 0; i < list.size(); i++) {
                  System.out.println("("+list.get(i)+","+list.get(++i)+")");
              }
                  //还要输入多组数据呢
              lists.clear();
         }
        }

        //回溯函数
     public static void backtracking(int[][] maze,int i,int j,int x,int y,List<Integer> list,int[][] hp){
                //在这些条件下，返回
         if(i<0||j<0||i==x||j==y||hp[i][j]==1||maze[i][j]==1){
             return;
         }
                //到最右下的元素了
         if(i==x-1&&j==y-1){
             //或许因为最后一个也要添进去
             list.add(i);
             list.add(j);
             lists.add(new ArrayList<Integer>(list));
             list.remove(list.size()-1);//将list的终点坐标清除，回溯法的核心就是办完事（达到目标）一定要完全还原之前的状态
             list.remove(list.size()-1);//这里的list是引用传递，所以不清除的话会一直带着终点坐标
             return;
         }

             list.add(i);
             list.add(j);
             hp[i][j]=1;
                         //上下左右
             backtracking(maze,i,j+1,x,y,list,hp);
             backtracking(maze,i+1,j,x,y,list,hp);
             backtracking(maze,i,j-1,x,y,list,hp);
             backtracking(maze,i-1,j,x,y,list,hp);
             hp[i][j]=0;
             list.remove(list.size()-1);//回溯
             list.remove(list.size()-1);

     }
}

借鉴了一位高赞回答