Java DFS with some optimization, 162ms


  • 0
    A

    Guys, 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)
    }
    

Log in to reply
 

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