摘要：題目鏈接和上一題不一樣的是這道題要求最短的路徑，普通的遍歷和都是可以做的，但是求最短路徑的話還是用。這里相當(dāng)于每個點有至多條相連，每條的就是到墻之前的長度。

題目鏈接：https://leetcode.com/problems...

又是圖的遍歷問題，就是簡單的遍歷，所以dfs和bfs都可以做，復(fù)雜度也是一樣的。這道題要求球不能停下來，即使碰到destination，必須是碰到wall才能停下來。

public class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        if(maze.length == 0 || maze[0].length == 0) return false;
        if(start[0] == destination[0] && start[1] == destination[1]) return true;
        
        m = maze.length; n = maze[0].length;
        boolean[][] visited = new boolean[m][n];
        return dfs(maze, start, destination, visited);
    }
    int m, n;
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private boolean dfs(int[][] maze, int[] cur, int[] dest, boolean[][] visited) {
        // already visited
        if(visited[cur[0]][cur[1]]) return false;
        // reach destination
        if(Arrays.equals(cur, dest)) return true;
        
        visited[cur[0]][cur[1]] = true;
        for(int[] dir : dirs) {
            int nx = cur[0], ny = cur[1];
            while(notWall(nx + dir[0], ny + dir[1]) && maze[nx+dir[0]][ny+dir[1]] != 1) {
                nx += dir[0]; ny += dir[1];
            }
            if(dfs(maze, new int[] {nx, ny}, dest, visited)) return true;
        }
        return false;
    }
    
    private boolean notWall(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}

題目鏈接：https://leetcode.com/problems...

和上一題不一樣的是：這道題要求最短的路徑，普通的遍歷dfs和bfs都是可以做的，但是求最短路徑的話還是用Dijksra。這里相當(dāng)于每個點有至多4條edge相連，每條edge的weight就是到墻之前的長度。

public class Solution {
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        // base case
        if(Arrays.equals(start, destination)) return 0;
        
        m = maze.length; n = maze[0].length;
        
        return shortestPath(maze, start, destination);
    }
    int m, n;
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    private int shortestPath(int[][] maze, int[] start, int[] destination) {
        // get the vertice has the minimum distance to start
        PriorityQueue minHeap = new PriorityQueue<>((a, b) -> a.distance - b.distance);
        minHeap.offer(new Node(start[0], start[1], 0));
        
        // map that contains information of node: distance to start point
        int[][] visited = new int[m][n];
        for(int[] arr : visited) Arrays.fill(arr, Integer.MAX_VALUE);
        
        while(!minHeap.isEmpty()) {
            Node cur = minHeap.poll();
            // find the shortest path
            if(cur.x == destination[0] && cur.y == destination[1]) return cur.distance;
            
            for(int[] dir : dirs) {
                int nx = cur.x, ny = cur.y;
                while(isInMaze(nx + dir[0], ny + dir[1]) && maze[nx + dir[0]][ny + dir[1]] != 1) {
                    nx += dir[0];  ny += dir[1];
                }
                int distance = cur.distance + Math.abs(nx - cur.x) + Math.abs(ny - cur.y);
                if(visited[nx][ny] > distance) {
                    minHeap.offer(new Node(nx, ny, distance));
                    visited[nx][ny] = distance;
                }
            }
        }
        return -1;
    }
    
    private boolean isInMaze(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
    
    class Node {
        int x;
        int y;
        // distance to start point
        int distance;
        Node(int x, int y, int distance) {
            this.x = x;
            this.y = y;
            this.distance = distance;
        }
    }
}