HJ43. 迷宫问题

刷题

题目：定义一个二维数组 N*M ，如 5 × 5 数组下所示：

int maze[5][5] = {0, 1, 0, 0, 0,
                  0, 1, 1, 1, 0,
                  0, 0, 0, 0, 0,
                  0, 1, 1, 1, 0,
                  0, 0, 0, 1, 0};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0]，既第一格是可以走的路。
数据范围：2≤n,m≤10， 输入的内容只包含 0≤val≤1

输入描述：输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
输出描述：左上角到右下角的最短路径，格式如样例所示。
链接：https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc

题目要求路线，考虑使用回溯法从左上角开始，向上下左右搜索。走到终点的时候，要不就把路径换一个地方存，要不就在后面回溯时根据结束标记判断一下，否则会把路径倒着一个个删掉，前功尽弃，/(ㄒoㄒ)/~~

public class Main {
    public static boolean isEnd = false;
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            int m = in.nextInt();
            int[][] map = new int[n][m];
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    map[i][j] = in.nextInt();
                }
            }
            //路径存储的集合
            List<Pos> path = new ArrayList<>();
            isEnd = false;
            backtrack(map, path,0, 0);
            for(Pos p : path){
                System.out.println(p.toString());
            }
        }
    }
    private static void backtrack(int[][] map, List<Pos> path, int x, int y) {
        //越界了
        if (x<0 || x>map.length-1 || y<0 || y>map[0].length-1) return;
        //撞墙了 或者 到终点了
        if (map[x][y] == 1 || isEnd) return;
        //结束条件
        if(x==map.length-1 && y==map[0].length-1) {
            path.add(new Pos(x, y));//添加终点
            isEnd = true;
            return;
        };
        map[x][y] = 1;//标记走过的点，以防倒着走回去
        path.add(new Pos(x, y));
        //以 x,y 为中心，向上下左右搜索
        backtrack(map, path, x-1, y);
        backtrack(map, path, x+1, y);
        backtrack(map, path, x, y-1);
        backtrack(map, path, x, y+1);
        map[x][y] = 0;//回溯，恢复到之前的点的状态
        if (!isEnd)//如果已经到右下角了，路径就不移除了，后面还要打印
            path.remove(path.size()-1);//回溯，移除路径最后一个点
    }
    public static class Pos{
        int x;
        int y;
        public Pos(int x, int y){
            this.x = x;
            this.y = y;
        }
        public String toString() {
            return "("+x+","+y+")";
        }
    }
}

因为迷宫只有一条通道，不考虑最短路径的问题，否则需要在找到终点后比一下找出最短路径，参见网友解法