490. The Maze && 505. The Maze II

摘要：题目链接和上一题不一样的是这道题要求最短的路径，普通的遍历和都是可以做的，但是求最短路径的话还是用。这里相当于每个点有至多条相连，每条的就是到墙之前的长度。

题目链接：https://leetcode.com/problems...

又是图的遍历问题，就是简单的遍历，所以dfs和bfs都可以做，复杂度也是一样的。这道题要求球不能停下来，即使碰到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。这里相当于每个点有至多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;
        }
    }
}