Home Computer Science Java Algorithm

788 · The Maze II - LintCode

# Description

There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up , down , left or right , but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the ball's start position, the destination and the maze, find the shortest distance for the ball to stop at the destination. The distance is defined by the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included). If the ball cannot stop at the destination, return -1.

The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.

# Example

Example 1:
	Input:  
	(rowStart, colStart) = (0,4)
	(rowDest, colDest)= (4,4)
	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

	Output:  12
	
	Explanation:
	(0,4)->(0,3)->(1,3)->(1,2)->(1,1)->(1,0)->(2,0)->(2,1)->(2,2)->(3,2)->(4,2)->(4,3)->(4,4)


Example 2:
	Input:
	(rowStart, colStart) = (0,4)
	(rowDest, colDest)= (0,0)
	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

	Output:  6
	
	Explanation:
	(0,4)->(0,3)->(1,3)->(1,2)->(1,1)->(1,0)->(0,0)

# Solution

之前的那題迷宮 問的是，能不能到達終點。
這一題多問的是，它到終點的最短距離是多遠？
和其他簡單圖不一樣的是，球每一次都走好幾步，撞牆才會停然後轉方向，所以說我不是一次走一步，而是一次走好幾步。

// 建一個 point 紀錄當時點的狀態
class Point {
    int x, y, l;
    public Point(int x, int y, int l){
        this.x = x;
        this.y = y;
        this.l = l; // 走多遠了
    }
}
public class Solution {
    /**
     * @param maze: the maze
     * @param start: the start
     * @param destination: the destination
     * @return: the shortest distance for the ball to stop at the destination
     */
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        // 用來紀錄從起點到我走到的點 /（終點）到多少步
        int[][] res = new int[maze.length][maze[0].length];
        for (int i = 0; i < maze.length; i++){
           for (int j = 0; j < maze[0].length; j++){
               // 初始化每一個位置
               res[i][j] = Integer.MAX_VALUE;
           }
        }
		// 我把點的狀態放到 Queue 裡
        Queue<Point> queue = new LinkedList<>();
        // 設 l = 0, 一步都沒有走到
        queue.offer(new Point(start[0], start[1], 0));
		//directions
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        while (!queue.isEmpty()){
            Point cur = queue.poll();
			// 先判斷我現在的點，如果長度比我的結果的長度還大的話
			// 說明我現在的點並不是最短距離了，沒必要走現在的點
            if (cur.l >= res[cur.x][cur.y]){
                continue;
            }
            // 把結果存到 ｛現在的點｝
            res[cur.x][cur.y] = cur.l;
           // 擴展
            for (int i = 0; i < 4; i++){  
                int nextx = cur.x;
                int nexty = cur.y;
                int l = cur.l;             
                while (nextx >= 0 && nextx < maze.length && 
                    nexty >= 0 && nexty < maze[0].length && maze[nextx][nexty] == 0){
                        nextx += dx[i];
                        nexty += dy[i];
                        l++;
                    }
                    // 退出 while means ball is outside /in the wall.
                    nextx -= dx[i];
                    nexty -= dy[i];
                    l--;
					// 放新一個點的狀態
                    queue.offer(new Point(nextx, nexty, l));
            }
         
        }
      
        return res[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 : res[destination[0]][destination[1]];
    }
}