用Java写一个迷宫问题

以下是一个简单的Java迷宫问题求解程序：

import java.util.*;

public class MazeSolver {
    private static final char WALL = '#';
    private static final char PATH = '.';
    private static final char START = 'S';
    private static final char END = 'E';

    private static int rows;
    private static int cols;
    private static char[][] maze;
    private static int startX;
    private static int startY;
    private static int endX;
    private static int endY;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入迷宫的行数和列数
        System.out.print("请输入迷宫的行数：");
        rows = scanner.nextInt();
        System.out.print("请输入迷宫的列数：");
        cols = scanner.nextInt();

        // 初始化迷宫
        maze = new char[rows][cols];
        System.out.println("请输入迷宫的地图，用#表示墙，.表示通路，S表示起点，E表示终点：");
        for (int i = 0; i < rows; i++) {
            String line = scanner.next();
            for (int j = 0; j < cols; j++) {
                maze[i][j] = line.charAt(j);
                if (maze[i][j] == START) {
                    startX = i;
                    startY = j;
                } else if (maze[i][j] == END) {
                    endX = i;
                    endY = j;
                }
            }
        }

        // 求解迷宫
        List<Point> path = solveMaze(startX, startY);

        // 输出路径
        if (path == null) {
            System.out.println("迷宫无解！");
        } else {
            System.out.println("迷宫的解为：");
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (maze[i][j] == WALL) {
                        System.out.print(WALL);
                    } else if (path.contains(new Point(i, j))) {
                        System.out.print(PATH);
                    } else if (maze[i][j] == START) {
                        System.out.print(START);
                    } else if (maze[i][j] == END) {
                        System.out.print(END);
                    }
                }
                System.out.println();
            }
        }
    }

    private static List<Point> solveMaze(int x, int y) {
        // 判断当前位置是否合法
        if (x < 0 || x >= rows || y < 0 || y >= cols || maze[x][y] == WALL || maze[x][y] == PATH) {
            return null;
        }

        // 到达终点，返回空路径
        if (x == endX && y == endY) {
            return new ArrayList<>();
        }

        // 标记当前位置已经走过
        maze[x][y] = PATH;

        // 递归求解四个方向
        List<Point> path = solveMaze(x - 1, y);
        if (path != null) {
            path.add(0, new Point(x, y));
            return path;
        }

        path = solveMaze(x + 1, y);
        if (path != null) {
            path.add(0, new Point(x, y));
            return path;
        }

        path = solveMaze(x, y - 1);
        if (path != null) {
            path.add(0, new Point(x, y));
            return path;
        }

        path = solveMaze(x, y + 1);
        if (path != null) {
            path.add(0, new Point(x, y));
            return path;
        }

        return null;
    }

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == this) {
                return true;
            }
            if (!(obj instanceof Point)) {
                return false;
            }
            Point other = (Point) obj;
            return this.x == other.x && this.y == other.y;
        }
    }
}

这个程序使用递归的方式求解迷宫问题。输入迷宫的行数、列数和地图后，程序会从起点开始递归求解四个方向（上、下、左、右），如果找到终点则返回一条路径，否则返回空路径。在递归过程中，程序会将已经走过的路径标记为“.”，避免重复走过同一条路径。最后，程序会输出求解得到的路径。如果迷宫无解，则输出“迷宫无解！”。