JAVA, Accepted DFS


  • 4
    I
    static final int[] DIRS = {0, 1, 0, -1, 0};
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int[][] dist = new int[maze.length][maze[0].length];
        dist[start[0]][start[1]] = 1;
        dfs(start[0], start[1], destination, maze, dist);
        return dist[destination[0]][destination[1]] - 1;
    }
    void dfs(int row, int col, int[] dest, int[][] maze, int[][] dist) {
        if (row == dest[0] && col == dest[1]) return;
        int m = maze.length, n = maze[0].length;
        for (int d = 0; d < 4; ++d) {
            int i = row, j = col, p = DIRS[d], q = DIRS[d + 1], len = dist[row][col];
            while (i + p >= 0 && i + p < m && j + q >= 0 && j + q < n && maze[i + p][j + q] == 0) {
                i += p;
                j += q;
                len++;
            }
            if (dist[i][j] > 0 && len >= dist[i][j]) continue;
            dist[i][j] = len;
            dfs(i, j, dest, maze, dist);
        }
    }
    
    

  • 0
    A

    I think this solution is TLE sometimes


  • 0

    I got a similar idea with yours but mine solution is TLE, could you please help me?

    public class Solution {
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
    int[][] visited = new int[maze.length][maze[0].length];
    visited[start[0]][start[1]] = 1;
    dfs(maze, start, destination, visited);
    return visited[destination[0]][destination[1]] - 1;
    }

    private void dfs(int[][] maze, int[] cur, int[] dest, int[][] visited) {
        if(cur[0]==dest[0] && cur[1]==dest[1]) return;
        for(int[] dir : dirs) {
            int m = maze.length, n = maze[0].length;
            int nx = cur[0], ny = cur[1];
            int p2p = visited[cur[0]][cur[1]];
            while(nx + dir[0]>=0 && nx + dir[0]<m && ny + dir[1]>=0 && ny + dir[1]<n && maze[nx+dir[0]][ny+dir[1]] == 0) {
                nx += dir[0]; ny += dir[1]; p2p ++;
            }
            if(visited[nx][ny] > 0 && p2p > visited[nx][ny]) continue;
            visited[nx][ny] = p2p;
            dfs(maze, new int[] {nx, ny}, dest, visited);
        }
    }
    

    }


  • 0
    A

    @zhangxian1511 I feel like for this question, if we use DFS, it is pretty easy to get TLE. You can compare DFS with BFS solution and their ideas are pretty similar. So I would doubt that if it is because of the test cases.


  • 0

    @Anylnb Thanks a lot.


  • 0

    My AC C++ dfs is 549ms while bfs is 29ms, dfs is not optimal for this problem.


  • 0
    B

    My dfs code only passes 80% of the cases, anybody have comments on where the flaw in logic is?

    '''
    public class Solution {
    final int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
    for(int i=0;i<maze.length;i++){
    for(int j=0;j<maze[0].length;j++)
    if(maze[i][j]==1) maze[i][j]=-1;
    }
    int min = dfs(maze, start[0], start[1], destination);
    return min==Integer.MAX_VALUE?-1:min;
    }

    public int dfs(int[][] maze, int row, int col, int[] dest){
        if(row==dest[0]&&col==dest[1])
            return 0;
        //ive visted here before
        if(maze[row][col]>0)
            return maze[row][col];
        int thisMin = Integer.MAX_VALUE;
        maze[row][col] = Integer.MAX_VALUE;
        for(int[] dir:dirs){
            int r = row;
            int c = col;
            int length = 0;
            while(!(r<0||r>=maze.length||c<0||c>=maze[0].length)&&(maze[r][c]>=0)){
                length++;
                r+=dir[0];
                c+=dir[1];
            }
            r-=dir[0];
            c-=dir[1];
            length--;
            int thisPath = dfs(maze, r, c, dest);
            if(thisPath!=Integer.MAX_VALUE)
                thisMin = Math.min(thisMin, thisPath+length);
        }
        maze[row][col] = thisMin;
        //System.out.println(row+","+col+"  "+thisMin);
        return thisMin;
    }
    

    }
    '''


  • 0
    C

    @Anylnb I agree, they have similar ideas. But why the time difference is so huge...


  • 0
    A
    This post is deleted!

  • 0
    A

    @codingFun , if we add a "from" int variable, to avoid going back to the direction where we came from, it can save several hundred ms.
    like this code below. The running time is 162ms

    class Solution {
    private int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};

    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
    	int[][] visited = new int[maze.length][maze[0].length];
    	findDistance(maze, start, destination, 0, visited, 10);
    	return visited[destination[0]][destination[1]] == 0 ? -1 : visited[destination[0]][destination[1]];
    }
    
    private void findDistance(int[][] maze, int[] start, int[] destination, int curDist, int[][] visited, int from) {
    	if (visited[start[0]][start[1]] != 0 && visited[start[0]][start[1]] <= curDist) {
    		return;
    	}
    	visited[start[0]][start[1]] = curDist;
    	if (Arrays.equals(start, destination)) {
    		return;
    	}
        int cantGo = from % 2 == 1 ? from - 1 : from + 1;
    	//try to roll in all four direction
    	for (int i = 0; i < 4; i++) {
            if (i == cantGo) {
                continue;
            }
    		int newDist = curDist;
    		int x = start[0];
    		int y = start[1];
    		while (canRoll(maze,x, y, i)) {
    			x += dir[i][0];
    			y += dir[i][1];
    			newDist++;
    		}
    		if (start[0] != x ||start[1] != y) {
    			findDistance(maze, new int[]{x,y}, destination, newDist, visited, i);
    		}
    	}
    }
    
    private boolean canRoll(int[][] maze, int x, int y, int i) {
    	x += dir[i][0];
    	y += dir[i][1];
    	boolean canRoll = (x >= 0 && x < maze.length && y >= 0 && y < maze[0].length && maze[x][y] != 1);
    	return canRoll;
    }
    //Time complexity: O(n * m)
    //Space complexity: O(n * m)
    

    }


  • 0
    F

    My DFS version. Convert from bfs, also slow...

    class Solution {
        public int shortestDistance(int[][] maze, int[] start, int[] destination) {
            int m = maze.length, n = maze[0].length, res = Integer.MAX_VALUE;
            int[][] dp = new int[m][n];
            for (int[] d: dp) {
                Arrays.fill(d, Integer.MAX_VALUE);
            }
            dp[start[0]][start[1]] = 0;
            helper(maze, start, dp);
            return dp[destination[0]][destination[1]] == Integer.MAX_VALUE? -1 : dp[destination[0]][destination[1]];
        }
        public void helper(int[][] maze, int[] start, int[][] dp) {
            int[][] dir = new int[][]{{1, -1, 0, 0}, {0, 0, 1, -1}};
            int m = maze.length, n = maze[0].length;
            for (int i = 0; i < 4; i++) {
                    int row = start[0];
                    int col = start[1];
                    int dist = dp[row][col];
                    while (row >= 0 && row < m && col >= 0 && col < n && maze[row][col] != 1) {
                        row += dir[0][i];
                        col += dir[1][i];
                        dist++;
                    }
                    row -= dir[0][i];
                    col -= dir[1][i];
                    dist--;
                    if (dist < dp[row][col]) { 
                        dp[row][col] = dist;
                        helper(maze, new int[]{row, col}, dp);
                    }
            }
        }
    }
    

  • 0
    X

    @AllenZzh Though this help speed dfs up, in bfs version we didn't add this constraint (which means it also considers going back to the direction where we came from) while bfs still run much faster even compared with your modified version here...


Log in to reply
 

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