题解 | #迷宫问题#

import java.util.Scanner;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
 // 不用队列，用Arraylist和LinkedList
    public int x;
    public int y;
    public Main parent;
    public void setX(int x) {
        this.x = x;
    }
    public int getX() {
        return this.x;
    }
    public void setY(int y) {
        this.y = y;
    }
    public int getY() {
        return this.y;
    }
    public void setParent(Main parent) {
        this.parent = parent;
    }
    public Main getParent() {
        return this.parent;
    }

    public static boolean bfs(ArrayList<Main> zt, LinkedList<Main> open,
                              int maze[][], int N, int M, int[][] visit) {

        while (!open.isEmpty()) {//节点的上下左右只是open的一部分
            int posX = open.get(0).x;
            int posY = open.get(0).y;
            zt.add(open.get(0));//close表存储路径
            if (posX == (N - 1) && posY == (M - 1)) {
                return true;
            }
            for (int i = -1; i < 2; i++)
                for (int j = -1; j < 2; j++) {
                    if (i != j && i != -1 * j) {//满足条件的i,j组合为{-1,0},{0,-1},{1,0},{0,1}，即上下左右四个方向
                        posX = open.get(0).x + i;
                        posY = open.get(0).y + j;
                        if (posX < N && posX >= 0 && posY < M && posY >=0) {
                            if (maze[posX][posY] == 0 && visit[posX][posY] == 0 ) {
                                Main migongtemp = new Main();
                                migongtemp.setX(posX);
                                migongtemp.setY(posY);
                                migongtemp.setParent(open.get(0));
                                visit[posX][posY] = 1;
                                open.add(migongtemp);
                            }

                        }
                    }
                }
            open.remove(0);
        }
        return false;
    }

    public static void printRoad(ArrayList<Main> zt) {
        ArrayList<String> road = new ArrayList();
        Main migongtemp = zt.get(zt.size() - 1);
        //向前追溯路径
        while (migongtemp.parent != null) {
            road.add("(" + migongtemp.x + "," + migongtemp.y + ")");
            migongtemp = migongtemp.parent;
        }
        if (migongtemp.parent == null) {
            road.add("(" + migongtemp.x + "," + migongtemp.y + ")");
        }
        //向后打印
        for(int i = road.size()-1;i>0;i--){
            System.out.println(road.get(i));
        }
        System.out.println(road.get(0));
    }

    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        int[][] maze = new int[11][11];
        int[][] visit = new int[11][11];
        while (scan.hasNext()) {
            ArrayList<Main> zt = new ArrayList ();//就是close 表，存路径
            LinkedList<Main> open = new LinkedList ();//bfs遍历表，存当前待遍历节点,LinkedList好删除头节点,Queue是基于LinkedList
            int N = scan.nextInt();
            int M = scan.nextInt();
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    maze[i][j] = scan.nextInt();
                }
            }
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    visit[i][j] = maze[i][j];
                }
            }
            Main migongtemp = new Main();
            migongtemp.setX(0);
            migongtemp.setY(0);
            open.add(migongtemp);
            if (bfs(zt, open, maze, N, M, visit)) {
                printRoad(zt);
            }
        }
    }
}