The Maze

BFS, 注意四个方向可以用一个while代替。

public class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        if(maze==null || maze.length==0) return false;
        Queue<int[]> queue = new LinkedList<int[]>();
        HashSet<String> visited = new HashSet<String>();
        queue.add(start); visited.add(Arrays.toString(start));
        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            //System.out.println(Arrays.toString(cur));
            if(cur[0]==destination[0]&&cur[1]==destination[1]) return true;
            int x = cur[0]; int y=cur[1];
            int tmpx=x; int tmpy=y; int[] tmpPt = new int[2];
            while(tmpx>=0&&maze[tmpx][tmpy]!=1) tmpx--;
            tmpPt[0] = tmpx+1; tmpPt[1]=tmpy;
            if(!visited.contains(Arrays.toString(tmpPt))){
                queue.add(tmpPt); visited.add(Arrays.toString(tmpPt));
            }

            tmpx=x; tmpy=y; tmpPt = new int[2];
            while(tmpx<maze.length&&maze[tmpx][tmpy]!=1) tmpx++;
            tmpPt[0] = tmpx-1; tmpPt[1]=tmpy;
            if(!visited.contains(Arrays.toString(tmpPt))){
                queue.add(tmpPt); visited.add(Arrays.toString(tmpPt));
            }

            tmpx=x; tmpy=y; tmpPt = new int[2];
            while(tmpy>=0&&maze[tmpx][tmpy]!=1) tmpy--;
            tmpPt[0] = tmpx; tmpPt[1]=tmpy+1;
            if(!visited.contains(Arrays.toString(tmpPt))){
                queue.add(tmpPt); visited.add(Arrays.toString(tmpPt));
            }

            tmpx=x; tmpy=y; tmpPt = new int[2];
            while(tmpy<maze[0].length&&maze[tmpx][tmpy]!=1) tmpy++;
            tmpPt[0] = tmpx; tmpPt[1]=tmpy-1;
            if(!visited.contains(Arrays.toString(tmpPt))){
                queue.add(tmpPt); visited.add(Arrays.toString(tmpPt));
            }
        }
        return false;
    }
}

public class Solution {
    class Point {
        int x,y;
        public Point(int _x, int _y) {x=_x;y=_y;}
    }
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int m=maze.length, n=maze[0].length;
        if (start[0]==destination[0] && start[1]==destination[1]) return true;
        int[][] dir=new int[][] {{-1,0},{0,1},{1,0},{0,-1}};
        boolean[][] visited=new boolean[m][n];
        LinkedList<Point> list=new LinkedList<>();
        visited[start[0]][start[1]]=true;
        list.offer(new Point(start[0], start[1]));
        while (!list.isEmpty()) {
            Point p=list.poll();
            int x=p.x, y=p.y;
            for (int i=0;i<4;i++) {
                int xx=x, yy=y;
                while (xx>=0 && xx<m && yy>=0 && yy<n && maze[xx][yy]==0) {
                    xx+=dir[i][0];
                    yy+=dir[i][1];
                }
                xx-=dir[i][0];
                yy-=dir[i][1];
                if (visited[xx][yy]) continue;
                visited[xx][yy]=true;
                if (xx==destination[0] && yy==destination[1]) return true;
                list.offer(new Point(xx, yy));
            }
        }
        return false;

    }
}

The Maze II

很好的一道题，考察了BFS和单原点最短路径（dijiestra）

• PriorityQueue维护下一个取出的节点
• distance［］［］维护单原点到当前（i，j）的距离
  • 如果搜索的距离小于当前distance［］［］，则加入priority queue。
  • 否则不加入。

public class Solution {

    class Point implements Comparable<Point>{
        int x;
        int y;
        int l;
        public Point(int x, int y, int l){
            this.x = x;
            this.y = y;
            this.l = l;
        }

        public int compareTo(Point p1){
            return this.l - p1.l;
        }

        public String toString(){
            return this.x+" "+this.y;
        }
    }

    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        if(maze==null || maze.length==0) return -1;
        int[][] dist = new int[maze.length][maze[0].length];
        for(int[] arr : dist) Arrays.fill(arr, Integer.MAX_VALUE);
        PriorityQueue<Point> pq = new PriorityQueue<Point>();
        HashSet<String> visited = new HashSet<String>();
        pq.offer(new Point(start[0], start[1], 0)); dist[start[0]][start[1]] = 0;
        int[][] direct = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};

        while(!pq.isEmpty()){
            Point cur = pq.poll();
            if(visited.contains(cur.toString())) continue;
            visited.add(cur.toString());
            if(cur.x==destination[0]&&cur.y==destination[1]) return cur.l;
            int x = cur.x; int y=cur.y;

            for(int i=0;i<4;i++){
                int tmpx=x; int tmpy=y; int d=cur.l-1;
                while(tmpx>=0&&tmpx<maze.length&&tmpy>=0&&tmpy<maze[0].length&&maze[tmpx][tmpy]!=1){
                    tmpx+=direct[i][0];
                    tmpy+=direct[i][1];
                    d++;
                }
                tmpx-=direct[i][0]; tmpy-=direct[i][1];
                if(d<dist[tmpx][tmpy]){
                    pq.offer(new Point(tmpx, tmpy, d));
                    dist[tmpx][tmpy] = d; 
                }
            }
        }

        // for(int[] arr : dist){
        //     System.out.println(Arrays.toString(arr));
        // }

        return -1;
    }

}

The Maze III

在家里效率真的好低啊，一会儿就躺床上睡觉了。得赶紧找到状态。

这道题一开始延续了Maze II的思路，开了distance［］［］，visited［］［］二维数组，路径string存在Point里。用minD维护找到的最短距离，所有结果储存在ans数组里，排序找出结果。所有步骤都中规中矩，最后没有debug，写法比较繁琐。

论坛里给出了更简单直接的方式，开Points［］［］数组，Point comparator比较当前的距离和路径，取较小值。PriorityQueue中只处理比已得到Point“短小”的Point（干净有效的剪枝）。

碰到hole的干净有效处理方式是让ball停在下一个有效位置上，正常情况下是一个方向的尽头，加一个特殊条件判断是否掉入hole中，掉入hole，hole是有效节点。

public class Solution {
    class Point implements Comparable<Point>{
        int x;
        int y;
        int l;
        String path;
        public Point(int x, int y, int l, String str){
            this.x = x;
            this.y = y;
            this.l = l;
            path = new String(str);
        }
        public int compareTo(Point p1){
            if(this.l!=p1.l) return this.l-p1.l;
            return this.path.compareTo(p1.path);
        }
        public String toString(){
            return this.x+" "+this.y;
        }
    }

    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        if(maze==null || maze.length==0) return "";
        int[][] direct = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
        char[] directC = new char[]{'u','d','r','l'};
        Point[][] points = new Point[maze.length][maze[0].length];


        for(int i=0;i<maze.length;i++)
            for(int j=0;j<maze[0].length;j++){
                points[i][j] = new Point(i, j, Integer.MAX_VALUE, "");
            }
        //points[ball[0]][ball[1]].l = 0;
        PriorityQueue<Point> pq = new PriorityQueue<Point>();
        pq.offer(new Point(ball[0], ball[1], 0, "")); 

        while(!pq.isEmpty()){
            Point cur = pq.poll();
            if(points[cur.x][cur.y].compareTo(cur)<=0) continue;
            points[cur.x][cur.y] = cur;
            int x = cur.x; int y=cur.y;

            for(int i=0;i<4;i++){
                int tmpx=x; int tmpy=y; int d=cur.l; 
                while(tmpx>=0&&tmpx<maze.length&&tmpy>=0&&tmpy<maze[0].length&&(maze[tmpx][tmpy]!=1&&(tmpx!=hole[0] ||tmpy!=hole[1]))){
                    tmpx+=direct[i][0];
                    tmpy+=direct[i][1];
                    d++;
                }
                if(tmpx!=hole[0] || tmpy!=hole[1]){
                    tmpx-=direct[i][0];
                    tmpy-=direct[i][1];
                    d--;
                }
                pq.offer(new Point(tmpx, tmpy, d, cur.path+directC[i]));
            }
        }
        for(int i=0;i<maze.length;i++){
            for(int j=0;j<maze[0].length;j++){
                System.out.print(points[i][j].l+" ");
            }
            System.out.println();
        }


        return points[hole[0]][hole[1]].l==Integer.MAX_VALUE?"impossible":points[hole[0]][hole[1]].path;
    }
}