Share my java DFS clear solution


  • 0
    T

    I failed to solve this problem during the contest, this solution I come out by referring solution from @chidong. (Thanks very much for sharing!) This is his post.

    I borrowed the most of main logic part and using instance variables to cache global variables (I very like this, it makes code very clear). The differences are I used the minimal distance to map to judge if I should continue to a direction, and also a Point class and an enum to cache distance information. I think it's helpful to make my code a bit more readable.

    The two helper classes contribute a bit more code, but main logic is very short.

    Hope this post can help. Following is my code.

    public class Solution {
        public enum D {
            UP(-1, 0, "u"),
            DOWN(1, 0, "d"),
            LEFT(0, -1, "l"),
            RIGHT(0, 1, "r");
            
            private D(int x, int y, String s){
                this.x = x;
                this.y = y;
                this.s = s;
            }
            public final int x;
            public final int y;
            public final String s;
        }
    
        public class Point {
            int x;
            int y;
            String path;
            int distance;
            
            public Point(int x, int y) {
                this.x = x;
                this.y = y;
                this.path = "";
                this.distance = 0;
            }
    
            public Point(Point p) {
                this.x = p.x;
                this.y = p.y;
                this.path = p.path;
                this.distance = p.distance;
            }
        }
    
        private Point shortest;
        private int[][] min;
        private int tx;
        private int ty;
    
        public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
           this.tx = hole[0];
           this.ty = hole[1];
           this.min = new int[maze.length][maze[0].length];
           Point p = new Point(ball[0], ball[1]);
           move(p, null, maze);
           return shortest == null ? "impossible" : shortest.path;
        }
    
        public void move(Point p, D d, int[][] maze) {
            if(d != null){
                if(min[p.x][p.y] != 0 && p.distance > min[p.x][p.y]){
                    return;
                }
                min[p.x][p.y] = p.distance;
                int x = p.x + d.x;
                int y = p.y + d.y;
                while(x >= 0 && x < maze.length && y >= 0 && y < maze[0].length && maze[x][y] == 0) {
                    p.x = x;
                    p.y = y;
                    p.distance++;
                    if(x == tx && y == ty) {
                        if(shortest == null 
                        || shortest.distance > p.distance 
                        || (shortest.distance == p.distance && shortest.path.compareTo(p.path) > 0)) {
                            shortest = p;
                            return;
                        }
                    }
                    x = x + d.x;
                    y = y + d.y;
                }
            }
            for(D nextD : d.values()){
                if(d != null) {
                    if((d == D.UP || d == D.DOWN) && (nextD == D.UP || nextD == D.DOWN)
                    || (d == D.LEFT || d == D.RIGHT) && (nextD == D.LEFT || nextD == D.RIGHT)){
                        continue; 
                    }
                }
                int nx = p.x + nextD.x;
                int ny = p.y + nextD.y;
              
                if(nx >= 0 && nx < maze.length && ny >= 0 && ny < maze[0].length && maze[nx][ny] == 0) {
                    Point nextP = new Point(p);
                    nextP.path += nextD.s;
                    move(nextP, nextD, maze);
                }
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.