maze

The Maze三重奏

490. The Maze

Approach 1: Depth First Search

int row;
int col;
int[][] maze;
int[][] dirs={{1,0},{-1,0},{0,1},{0,-1}};
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
    row=maze.length;
    col=maze[0].length;
    this.maze=maze;
    return dfs(start[0],start[1],destination,new boolean[row][col]);
}

boolean dfs(int i, int j, int[] end,boolean[][] visited){
    if(i==end[0] && j==end[1]){
        return true;
    }
    visited[i][j]=true;
    for (int[] dir : dirs) {
        int x=i+dir[0];
        int y=j+dir[1];
        while(x>=0 && x<row && y>=0 && y<col && maze[x][y]==0){
            x+=dir[0];
            y+=dir[1];
        }

       if(!visited[x-dir[0]][y-dir[1]] ){
            if(dfs(x-dir[0],y-dir[1],end,visited)){
                return true;
            }
        }
    }
    return false;
}

Approach 2: Breadth First Search

public boolean hasPath(int[][] maze, int[] start, int[] destination) {
    Deque<int[]> q=new LinkedList<>();
    int row=maze.length;
    int col=maze[0].length;
    boolean[][] visited=new boolean[row][col];
    int[][] dirs=new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    visited[start[0]][start[1]]=true;
    q.offer(start);
    while(!q.isEmpty()){
        int[] cur=q.poll();
        int i=cur[0];
        int j=cur[1];
        if(i==destination[0] && j==destination[1]){
            return true;
        }
        for (int[] dir : dirs) {
            int x=i+dir[0];
            int y=j+dir[1];
            while(x>=0 && x<row && y>=0 && y<col && maze[x][y]==0){
                x+=dir[0];
                y+=dir[1];
            }
            if(!visited[x-dir[0]][y-dir[1]]){
                visited[x-dir[0]][y-dir[1]]=true;
                q.offer(new int[]{x-dir[0],y-dir[1]});
            }
        }
    }
    return false;
}

505. The Maze II

DFS:

int row;
int col;
int[][] maze;
int[][] dirs={{1,0},{-1,0},{0,1},{0,-1}};
public int shortestDistance(int[][] maze, int[] start, int[] destination) {
    this.maze=maze;
    row=maze.length;
    col=maze[0].length;
    int[][] dist=new int[row][col];
    for (int[] ints : dist) {
        Arrays.fill(ints,Integer.MAX_VALUE);
    }
    dist[start[0]][start[1]]=0;
    dfs(start[0],start[1],destination,dist);
    return dist[destination[0]][destination[1]]==Integer.MAX_VALUE ? -1 : dist[destination[0]][destination[1]];
}

void dfs(int i, int j, int[] end,int[][] dist){
    if(i==end[0] && j==end[1]){
        return;
    }
    for (int[] dir : dirs) {
        int x=i+dir[0];
        int y=j+dir[1];
        int d=dist[i][j];
        while(x>=0 && x<row && y>=0 && y<col && maze[x][y]==0){
            x+=dir[0];
            y+=dir[1];
            d++;
        }
        if(d<dist[x-dir[0]][y-dir[1]]){
            dist[x-dir[0]][y-dir[1]]=d;
            dfs(x-dir[0],y-dir[1],end,dist);
        }
    }
}

BFS:

public int shortestDistance(int[][] maze, int[] start, int[] destination) {
    int row=maze.length;
    int col=maze[0].length;
    int[][] dirs={{0,1},{0,-1},{1,0},{-1,0}};
    Deque<int[]> q=new LinkedList<>();
    int[][] visited=new int[row][col];
    for (int[] ints : visited) {
        Arrays.fill(ints,Integer.MAX_VALUE);
    }
    q.offer(new int[]{start[0],start[1]});
    visited[start[0]][start[1]]=0;
    while(!q.isEmpty()){
        int size=q.size();
        while(size-->0){
            int[] cur=q.poll();
            int i=cur[0];
            int j=cur[1];
            for (int[] dir : dirs) {
                int x=i+dir[0];
                int y=j+dir[1];
                int dist=visited[i][j];
                while(x>=0 && x<row && y>=0 && y<col && maze[x][y]==0){
                    x+=dir[0];
                    y+=dir[1];
                    dist++;
                }
                //only add meaningful updates to queue
                if(dist<visited[x-dir[0]][y-dir[1]]){
                    visited[x-dir[0]][y-dir[1]]=dist;
                    q.offer(new int[]{x-dir[0],y-dir[1]});
                }
            }
        }
    }
    return visited[destination[0]][destination[1]]==Integer.MAX_VALUE ? -1 : visited[destination[0]][destination[1]];
}

499. The Maze III

遍历所有可能，直到不可能出现更优路线

class Node implements Comparable<Node>{
    int i;
    int j;
    int dist;
    String path;

    Node(int i, int j) {
        this.i = i;
        this.j = j;
        this.dist = Integer.MAX_VALUE;
        this.path = "impossible";
    }

    Node(int i, int j, int dist, String path){
        this.i=i;
        this.j=j;
        this.dist=dist;
        this.path=path;
    }

    @Override
    public int compareTo(Node o) {
        return dist==o.dist ? path.compareTo(o.path) : dist-o.dist;
    }
}
public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
    int row= maze.length;
    int col=maze[0].length;
    Node[][] arr=new Node[row][col];
    String[] dir=new String[]{"u","d","l","r"};
    int[] dx=new int[]{-1,1,0,0};
    int[] dy=new int[]{0,0,-1,1};
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            arr[i][j]=new Node(i,j);
        }
    }
    Deque<Node> q=new LinkedList<>();
    q.offer(new Node(ball[0],ball[1],0,""));
    while(!q.isEmpty()){
        Node cur=q.poll();
        int i=cur.i;
        int j=cur.j;
        int dist=cur.dist;
        String path=cur.path;
        if(cur.compareTo(arr[i][j])>=0){
            continue;
        }
        arr[i][j]=cur;
        for (int k = 0; k < 4; k++) {
            int x=i;
            int y=j;
            int d=0;
            while(x>=0 && x<row && y>=0 && y<col && (x!=hole[0] || y!=hole[1]) && maze[x][y]==0){
                x+=dx[k];
                y+=dy[k];
                d++;
            }
            if(x!=hole[0] || y!=hole[1]){
                x-=dx[k];
                y-=dy[k];
                d--;
            }
            q.offer(new Node(x,y,dist+d,path+dir[k]));
        }
    }
    return arr[hole[0]][hole[1]].path;
}