[leetcode/lintcode 題解] 阿裡算法面試真題：迷宮

描述

在迷宮中有一個球，裡面有空的空間和牆壁。球可以通過滾上，下，左或右移動，

但它不會停止滾動直到撞到牆上。當球停止時，它可以選擇下一個方向。

給定球的起始位置，目的地和迷宮，确定球是否可以停在終點。

迷宮由二維數組表示。1表示牆和0表示空的空間。你可以假設迷宮的邊界都是牆。開始和目标坐标用行和列索引表示。

1.在迷宮中隻有一個球和一個目的地。

2.球和目的地都存在于一個空的空間中，它們最初不會處于相同的位置。

3.給定的迷宮不包含邊框(比如圖檔中的紅色矩形)，但是你可以假設迷宮的邊界都是牆。

5.迷宮中至少有2個空的空間，迷宮的寬度和高度都不會超過100。

線上評測位址：

領扣題庫官網

樣例1
輸入:
map = 
[
 [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]
]
start = [0,4]
end = [3,2]
輸出:
false           

樣例2
輸入:
map = 
[[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]
]
start = [0,4]
end = [4,4]
輸出:
true           

算法：BFS

簡單的BFS。由于沒有其他要求，我們隻需要在BFS的過程中在隊列裡記錄目前的坐标即可。

• 将地圖的起點放入隊列。
• 進行廣度優先搜尋。
  • 每一次取出隊首的元素，先判斷是否到了終點，到了終點直接退出。
  • 若沒有到達，往四周的方向滾，直到滾到牆為止。若到達的位置沒有被通路，那麼加入隊列中。
• 若整個過程都沒有通路到終點，傳回false即可。

上述也是一般BFS的執行過程。

複雜度分析

• 時間複雜度O(n∗m)O(n∗m)
• 有可能會周遊map上的每個點
• 空間複雜度O(n∗m)

public class Solution {

    /**

     * @param maze: the maze

     * @param start: the start

     * @param destination: the destination

     * @return: whether the ball could stop at the destination

     */

    public boolean hasPath(int[][] maze, int[] start, int[] destination) {

        // write your code here

        int n = maze.length;

        int m = maze[0].length;

        boolean[][] visited = new boolean[n][m];

        int[] dx = new int[]{0, -1, 0, 1};

        int[] dy = new int[]{1, 0, -1, 0};

        Queue<int[]> queue = new LinkedList<>();

        queue.offer(start);

        visited[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {

            int[] cur = queue.poll();

            if (cur[0] == destination[0] && cur[1] == destination[1]) {

                return true;

            }

            for (int direction = 0; direction < 4; direction++) {

                int nx = cur[0], ny = cur[1];

                while (nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] == 0) {

                    nx += dx[direction];

                    ny += dy[direction];

                }

                nx -= dx[direction];

                ny -= dy[direction];

                if (!visited[nx][ny]) {

                    visited[nx][ny] = true;

                    queue.offer(new int[]{nx, ny});

                }

            }

        }

        return false;

    }

}           

更多題解參考：

九章官網solution