Clear Java Accepted DFS Solution with Explanation


  • 12
    public class Solution {
        int min; //min distance to hole
        String minS; //min distance's path string
        int[] hole;
        int[][] maze; 
        int[][] map; //shortest distant traveling from ball to this point
        int[][] dirs = {{0,1},{-1,0},{1,0},{0,-1}}; //r, u, d, l
        public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
            this.min = Integer.MAX_VALUE; 
            this.minS = null;
            this.hole = hole; 
            this.maze = maze; 
            this.map = new int[maze.length][maze[0].length];
            for(int i = 0; i<map.length; i++) Arrays.fill(map[i], Integer.MAX_VALUE); 
            
            move(ball[0], ball[1], 0, "", -1);
            return (minS==null) ? "impossible" : minS;
        }
        
        private void move(int r, int c, int cnt, String path, int dir){//dir is a index of dirs 
            if(cnt > min || cnt > map[r][c]) return; //not a shortest route for sure 
            if(dir!=-1){//if not from start point 
                //add path 
                if(dir==0) path+='r';
                else if(dir==1) path+='u';
                else if(dir==2) path+='d';
                else path+='l';
        
                //roll along dir 
                while(r>=0 && r<maze.length && c>=0 && c<maze[0].length && maze[r][c]==0){
                    map[r][c] = Math.min(map[r][c], cnt); 
                    if(r==hole[0] && c==hole[1]){//check hole
                        if(cnt==min && path.compareTo(minS)<0){
                            minS=path;
                        }else if(cnt<min){
                            min = cnt; 
                            minS = path; 
                        }
                        return; 
                    }
                    r += dirs[dir][0];
                    c += dirs[dir][1];
                    cnt++;
                }
                r -= dirs[dir][0];//[r,c] is wall, need to walk back 1 step
                c -= dirs[dir][1];
                cnt--;
            }
            
            //hit wall (or start) -> try to turn
            for(int i = 0; i<dirs.length; i++){
                if(dir == i) continue;//dont keep going
                if(dir == (3-i)) continue;//dont go back
                int newR = r + dirs[i][0];
                int newC = c + dirs[i][1];
                if(newR>=0 && newR<maze.length && newC>=0 && newC<maze[0].length && maze[newR][newC]==0){//can go
                    move(r, c, cnt, path, i);
                }
            }
        }
    }
    

    Each time, first add the direction to the path, and then go with that direction, checking for hole along the way. When hit a wall, try to turn, and go with the new direction. For the starting point, don't "go", jump directly to "turn" part.


  • 0
    T

    Thanks for your code. It's really very clear and easy to read.


  • 3

    Nice code. Here is my DFS solution.

    public class Solution {
        int minStep;
        int m, n;
        String res;
        int[][] dirs = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
        String[] dirc = {"d", "r", "l", "u"}; // 0123
        public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
            this.m = maze.length; 
            this.n = maze[0].length;
            this.minStep = Integer.MAX_VALUE;
            this.res = null;
            boolean[][] vis = new boolean[m][n];
            vis[ball[0]][ball[1]] = true;
            
            dfs(ball[0], ball[1], maze, hole, vis, "", 0);
            
            return res == null ? "impossible" : res;
        }
        
        private void dfs(int i, int j, int[][] maze, int[] hole, boolean[][] vis, String route, int step) {
            if (step > minStep) return;
            if (i == hole[0] && j == hole[1]) {
                if (step == minStep && route.compareTo(res) < 0) {
                    res = route;
                } else if (step < minStep) {
                    minStep = step;
                    res = route;
                }
                vis[i][j] = false;
                return;
            }
            
            for (int d = 0; d < 4; d++) {
                // roll to the wall
                int x = i, y = j;
                while (x + dirs[d][0] >= 0 && x + dirs[d][0] < m && y + dirs[d][1] >= 0 && y + dirs[d][1] < n 
                    && maze[x + dirs[d][0]][y + dirs[d][1]] != 1) {
                    x += dirs[d][0];
                    y += dirs[d][1];
                    if (x == hole[0] && y == hole[1] || vis[x][y])  break;
                }
                if (!vis[x][y] && maze[x][y] == 0) {
                    vis[x][y] = true;
                    dfs(x, y, maze, hole, vis, route + dirc[d], step + Math.abs(x - i) + Math.abs(y - j));
                    vis[x][y] = false;
                }
            }
        }
    }
    

  • 0

    I really appreciated your int[][] map and use index of int[][] dirs to represent r,u,l,d, it simplified many works for me.

    Below is my BFS solution.

    But I am curious about why BFS is slower than DFS, I think this BFS solution is similar with Dijkstra's algorithm, it cannot be that slow theoretically speaking. Can you give me some hints, or maybe my implementation is not good enough to speed this BFS solution up?

    Ignore what I just said... This dame line slow my solution System.out.println(next.route);. Actually we can see the outputs from this line, that there are much less outputs by BFS solution.

    public class Solution {
        int[][] dirs = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
        char[] dirc = {'d', 'l', 'r', 'u'};
        public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
            int m = maze.length, n = maze[0].length;
            String minS = null;
            int min = Integer.MAX_VALUE;
            
            int[][] map = new int[m][n]; // min distance till this node
            for (int i = 0; i < m; i++) Arrays.fill(map[i], Integer.MAX_VALUE);
            
            Node start = new Node(ball[0], ball[1], 0, ""); // start point
            PriorityQueue<Node> q = new PriorityQueue();
            q.add(start);
            
            boolean[][] vis = new boolean[m][n]; // visited nodes
            while (!q.isEmpty()) {
                // extract min, get the cur position
                Node cur = q.poll();
                vis[cur.x][cur.y] = true;
                // try 4 dirs
                for (int d = 0; d < 4; d++) {
                    int x = cur.x, y = cur.y;
                    
                    // start point, or get the end point
                    while (x + dirs[d][0] < m && x + dirs[d][0] >= 0 && y + dirs[d][1] < n && y + dirs[d][1] >= 0
                        && maze[x + dirs[d][0]][y + dirs[d][1]] != 1) {
                            x += dirs[d][0];
                            y += dirs[d][1];
                            if (vis[x][y] || (x == hole[0] && y == hole[1])) break;
                    }
                    int step = cur.step + Math.abs(x - cur.x) + Math.abs(y - cur.y);
                    if (vis[x][y] || step > map[x][y]) continue;
                    // update distance 
                    map[x][y] = step; 
                    // next node
                    Node next = new Node(x, y, step, cur.route + dirc[d]);
                    
                   // System.out.println(next.route);  /// this damn line!!! slowed my solution...
                    
                    // reach the end
                    if (x == hole[0] && y == hole[1]) {
                        if (step == min && (minS == null || next.route.compareTo(minS) < 0)) {
                            minS = next.route;
                        } else if (step < min) {
                            min = step;
                            minS = next.route;
                        }
                        // if reach the end in this direction, we don't need to try other directions
                        break;
                    }
                    
                    q.add(next);
                }
            }
            return minS == null ? "impossible" : minS;
        }
        
        class Node implements Comparable<Node> {
            int x, y, step;
            String route; // a string formed by directions along the way
            public Node(int x, int y, int step, String route) {
                this.x = x;
                this.y = y;
                this.step = step;
                this.route = route;
            }
            
            public boolean equals(Node a, Node b) {
                return a.x == b.x && a.y == b.y;
            } 
            
            public int compareTo(Node that) {
                return this.step - that.step;
            }
        }
    }
    

  • 0
    N

    @zhugejunwei
    I liked your dfs solution, seems easier to understand to me.

    But I think there is something not that "correct" in your algorithm.
    If you change your code in the for loop instead of "d from 0 to 3", but "d from 3 to 0", you will get a incorrect result.
    Luckily, you choose the right sequence of the direction array for all test cases. However, the best way would be "d, l, r, u" since they increase in the sequence.

    Moreover, if you have the right sequence, you won't need to compare the path for the same steps. You will always find the shortest one first.

    correct me if I am wrong on this point, thanks


  • 1

    @notturno Actually that's not something you said luck.... I iterate in that specific order on purpose, so that I can output the route in a right order.

    There is no such luck I have ever met in this kind of question.

    And don't rely on luck, dude.


  • 0
    This post is deleted!

Log in to reply
 

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