题解 | #迷宫问题#

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Scanner;
import java.util.stream.Collectors;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String nextLine = in.nextLine();
            if (Objects.isNull(nextLine) || nextLine.equals("")) {
                break;
            }

            String[] s = nextLine.split(" ");
            int n = Integer.parseInt(s[0]);
            int m = Integer.parseInt(s[1]);
            // 记录迷宫
            int[][] maze = new int[n][m];
            for (int i = 0; i < n; i++) {
                String line = in.nextLine();
                String[] split = line.split(" ");
                for (int j = 0; j < m; j++) {
                    maze[i][j] = Integer.parseInt(split[j]);
                }
            }

            // 记录广域搜索中的队列
            List<BFS> record = new ArrayList<>();
            // 记录所有广域搜索的集合
            List<BFS> allRecord = new ArrayList<>();
            // 记录正向路径
            List<BFS> finalRecord = new ArrayList<>();
            // 广域搜索队列先加入起点
            record.add(new BFS(0, 0, 0, 0, 0));
            // 终点位置
            int targetX = n - 1;
            int targetY = m - 1;
            while (!record.isEmpty()) {
                // 如果有任何一个抵达了终点就退出循环
                if (record.stream()
                    .anyMatch(item -> item.x == targetX && item.y == targetY)) {
                    finalRecord = record.stream()
                        .filter(item -> item.x == targetX && item.y == targetY)
                        .collect(Collectors.toList());
                    break;
                }
                // 开始搜索，已经移动过的坐标则退出集合，抵达的坐标加入集合，并且记录为1
                // 迷宫为1的为不可以抵达的位置
                List<BFS> tempRecord = new ArrayList<>(record);
                record.clear();
                for (BFS currentBFS : tempRecord) {
                    allRecord.add(currentBFS);
                    List<BFS> searchResult = search(maze, currentBFS);
                    if (!searchResult.isEmpty()) {
                        record.addAll(searchResult);
                    }
                }
            }
            // 递归根据父节点找出路径
            while (finalRecord.stream()
                .noneMatch(item -> item.x == 0 && item.y == 0)) {
                finalRecord.add(0, dfs(finalRecord.get(0), allRecord));
            }
            finalRecord.forEach(item -> System.out.println("(" + item.getX() + "," + item.getY() + ")"));

        }
    }

    public static BFS dfs(BFS currentBFS, List<BFS> allRecord) {
        return allRecord.stream()
            .filter(item -> item.x.equals(currentBFS.getParentX()) && item.y.equals(currentBFS.getParentY()))
            .findFirst()
            .orElseGet(BFS::new);
    }

    // BFS搜索并返回下一步的集合
    public static List<BFS> search(int[][] maze, BFS currentBfs) {
        Integer currentBfsX = currentBfs.getX();
        Integer currentBfsY = currentBfs.getY();
        Integer currentBfsStep = currentBfs.getStep();
        Integer nextStep = currentBfsStep + 1;
        List<BFS> searchResult = new ArrayList<>();
        // 向下
        if (currentBfsX + 1 < maze.length && maze[currentBfsX + 1][currentBfsY] == 0) {
            maze[currentBfsX + 1][currentBfsY] = 1;
            searchResult.add(new BFS(nextStep, currentBfsX + 1, currentBfsY, currentBfsX, currentBfsY));
        }
        // 向右
        if (currentBfsY + 1 < maze[0].length && maze[currentBfsX][currentBfsY + 1] == 0) {
            maze[currentBfsX][currentBfsY + 1] = 1;
            searchResult.add(new BFS(nextStep, currentBfsX, currentBfsY + 1, currentBfsX, currentBfsY));
        }
        // 向上
        if (currentBfsX - 1 >= 0 && maze[currentBfsX - 1][currentBfsY] == 0) {
            maze[currentBfsX - 1][currentBfsY] = 1;
            searchResult.add(new BFS(nextStep, currentBfsX - 1, currentBfsY, currentBfsX, currentBfsY));
        }
        // 向左
        if (currentBfsY - 1 >= 0 && maze[currentBfsX][currentBfsY - 1] == 0) {
            maze[currentBfsX][currentBfsY - 1] = 1;
            searchResult.add(new BFS(nextStep, currentBfsX, currentBfsY - 1, currentBfsX, currentBfsY));
        }
        return searchResult;
    }

    // 广域搜索类
    public static class BFS {
        public Integer step = 0;

        // 当前在的坐标x
        public Integer x;

        // 当前在的坐标y
        public Integer y;

        // 父节点的坐标x
        public Integer parentX;

        // 父节点的坐标y
        public Integer parentY;

        public BFS() {
        }

        public BFS(Integer step, Integer x, Integer y, Integer parentX, Integer parentY) {
            this.step = step;
            this.x = x;
            this.y = y;
            this.parentX = parentX;
            this.parentY = parentY;
        }

        public Integer getParentX() {
            return parentX;
        }

        public void setParentX(Integer parentX) {
            this.parentX = parentX;
        }

        public Integer getParentY() {
            return parentY;
        }

        public void setParentY(Integer parentY) {
            this.parentY = parentY;
        }

        public Integer getStep() {
            return step;
        }

        public void setStep(Integer step) {
            this.step = step;
        }

        public Integer getX() {
            return x;
        }

        public void setX(Integer x) {
            this.x = x;
        }

        public Integer getY() {
            return y;
        }

        public void setY(Integer y) {
            this.y = y;
        }
    }
}