题解 | #迷宫问题#

package OnlineTest.normal;

import org.omg.PortableInterceptor.INACTIVE;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class MiGong {
    static int endX, endY;
    //装所有路径
    static ArrayList<List> path = new ArrayList<>();
    //装某一条路径的所有步子
    static List<String> OnePathStep = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int m = Integer.valueOf(s[0]);
        int n = Integer.valueOf(s[1]);
        //在迷宫外面围上一堵墙
        int[][] maze = new int[m + 2][n + 2];
        //第0行和第m+1行全是1
        for (int i = 0; i < n + 2; i++) {
            maze[0][i] = 1;
            maze[m + 1][i] = 1;
        }
        //第0列和第n+1列全是1
        for (int j = 0; j < m + 2; j++) {
            maze[j][0] = 1;
            maze[j][n + 1] = 1;
        }
        //构造迷宫
        int m_j = 1;
        do {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int n_i = 1;
            while (st.hasMoreTokens()) {
                maze[m_j][n_i] = Integer.valueOf(st.nextToken());
                n_i++;
            }
            m_j++;
        } while (br.ready());
        //print(maze);
        //设置终点
        endX = m;
        endY = n;

        dfs(maze, 1, 1);


        //打印步子
        for (List list : path) {
            for (Object objects : list) {
                System.out.println(objects.toString());
            }

        }
    }


    //找迷宫
    public static void dfs(int[][] maze, int x, int y) {
        //走过、越界、墙
        if (x == 0 || x == maze.length - 1 || y == 0 || y == maze[0].length - 1 || maze[x][y] == 2 || maze[x][y] == 1) {
            return;
        }
        //终点
        if (x == endX && y == endY) {
            maze[x][y] = 2;
            /*System.out.println("其中一条路径：");
            print(maze);*/
            OnePathStep.add(new location(x, y, 2).toString());


            path.add(new ArrayList(OnePathStep));
            //回溯
            maze[x][y] = 0;
            OnePathStep.remove(OnePathStep.size() - 1);
            return;
        } else {
            maze[x][y] = 2;
            OnePathStep.add(new location(x, y, 2).toString());

            //规定按照下右上左的方向遍历
            dfs(maze, x, y + 1);
            dfs(maze, x + 1, y);
            dfs(maze, x, y - 1);
            dfs(maze, x - 1, y);
            //回溯
            maze[x][y] = 0;
            OnePathStep.remove(OnePathStep.size() - 1);

        }


    }

    //打印二维数组，方便检查
    public static void print(int[][] a) {

        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }


}

    class location {
        int x,y, status;
        //2为走过了
        public location(int x, int y, int status) {
            this.x = x;
            this.y = y;
            this.status = status;
        }

        @Override
        public String toString() {
            return "(" + (x-1) +
                    "," +(y-1)+")"
                    ;
        }
    }