490.迷宫

由空地和墙组成的迷宫中有一个球。球可以向上下左右四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。

给定球的起始位置，目的地和迷宫，判断球能否在目的地停下。

迷宫由一个0和1的二维数组表示。1表示墙壁，0表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。

主要思路：

（1）广度优先搜索；

（2）将迷宫maze的元素置为2，来标识访问过的变换方向的位置；

（3）使用队列，存储各个可能变换方向的位置，并判断每个变换方向的位置是否是终点位置，若是，则返回true，否则，在没有访问过的情形下，压入到队列中；

public class Maze {
    // 定义四个方向：上、下、左、右
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int rows = maze.length;
        int cols = maze[0].length;

        // 记录访问过的位置
        boolean[][] visited = new boolean[rows][cols];

        // 使用队列进行BFS
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);
        visited[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];

            // 如果当前位置是目的地，返回true
            if (x == destination[0] && y == destination[1]) {
                return true;
            }

            // 尝试向四个方向滚动
            for (int[] dir : DIRECTIONS) {
                int newX = x;
                int newY = y;

                // 沿着当前方向滚动，直到遇到墙壁
                while (newX >= 0 && newX < rows && newY >= 0 && newY < cols && maze[newX][newY] == 0) {
                    newX += dir[0];
                    newY += dir[1];
                }

                // 回退一步，因为最后一步是撞墙
                newX -= dir[0];
                newY -= dir[1];

                // 如果这个位置没有被访问过，加入队列
                if (!visited[newX][newY]) {
                    visited[newX][newY] = true;
                    queue.offer(new int[]{newX, newY});
                }
            }
        }

        // 如果BFS结束还没有找到目的地，返回false
        return false;
    }

    public static void main(String[] args) {
        Maze solution = new Maze();
        int[][] maze = {
            {0, 0, 1, 0, 0},
            {0, 0, 0, 0, 0},
            {0, 0, 0, 1, 0},
            {1, 1, 0, 1, 1},
            {0, 0, 0, 0, 0}
        };
        int[] start = {0, 4};
        int[] destination = {4, 4};
        System.out.println(solution.hasPath(maze, start, destination)); // 输出: true
    }
}