[Java] [DFS] [Memoization] [Beats 85.71%] [15ms]


  • 2

    Consider rolling down, then left,right & up. One with the minimum steps is chosen. If multiple such exist, then choose the first of the ones considered in the above mentioned order. If no route exist, return -1.

    Stay away from infinite loops by marking starting locations.

    public class Solution {
    	private  String[][] directionsToHole;
    	private  int[][] shortestDistanceToHole;
    	public  String findShortestWay(int[][] maze, int[] ball, int[] hole) {
    		directionsToHole = new String[maze.length][maze[0].length];
    		shortestDistanceToHole = new int[maze.length][maze[0].length];
    		if(rollTheBall(maze,ball[0],ball[1],hole[0],hole[1])<0)
    			return "impossible";
    		return directionsToHole[ball[0]][ball[1]];
    	}
        
     	private int rollTheBall(int[][] maze, int ballRow, int ballColumn, int holeRow, int holeColumn){
    		// memoization step (i.e. if we have directions to reach hole from this point)
    		if(directionsToHole[ballRow][ballColumn]!=null)
    			return shortestDistanceToHole[ballRow][ballColumn];
    
    		maze[ballRow][ballColumn] = -2;	// Indicates that ball has been rolled from this point
    
    		int ro,co,steps,tr;
    		int rows = maze.length;
    		int cols = maze[0].length;
    		int[] dir = new int[4];
    		String[] path = new String[4];
    		int min = Integer.MAX_VALUE;
    
    		ro = ballRow;
    		co = ballColumn;
    		steps = 0;			// for counting the steps till a wall/boundary/hole is hit/found.
    
    		// Order of Rolling: down, left, right , up (lexicographically ordered).
    
    		while(ro<=rows-2){ // keep rolling down till boundary
    			if(ro+1 == holeRow && co == holeColumn){ // hole found
    				
    				steps++;
    				directionsToHole[ballRow][ballColumn] = "d";
    				// because we had set it as -2 in the starting, so reset it back
    				maze[ballRow][ballColumn] = 0;
    				// store the steps to the hole from starting point
    				shortestDistanceToHole[ballRow][ballColumn] = steps;
    				return steps;
    			}
    			if(maze[ro+1][co]==0){
    				ro++;
    				steps++;
    			}
    			else break;
    		}
    		
    		// if ball was rolled in the down direction and it was stopped by a
    		// boundary and by not any other starting point
    		if(ro>ballRow && !(ro<=rows-2 && maze[ro+1][co]==-2)){
    			tr = rollTheBall(maze,ro,co,holeRow,holeColumn);
    			if(tr>-1){
    				dir[0] = steps + tr;
    				min = Math.min(min, dir[0]);
    				path[0] = "d"+directionsToHole[ro][co];
    			}
    		}
    		
    		// Similarly for other three directions
    		steps=0;
    		ro = ballRow;
    		co = ballColumn;
    		while(co>=1){
    			if(ro == holeRow && co-1 == holeColumn){// hole found
    				steps++;
    				directionsToHole[ballRow][ballColumn] = "l";
    				maze[ballRow][ballColumn] = 0;
    				shortestDistanceToHole[ballRow][ballColumn] = steps;
    				return steps;
    			}
    			if(maze[ro][co-1]==0){
    				co--;
    				steps++;
    			}
    			else break;
    		}
    		if(co<ballColumn && !(co>=1 && maze[ro][co-1]==-2)){
    			tr = rollTheBall(maze,ro,co,holeRow,holeColumn);
    			if(tr>-1){
    				dir[1] = steps + tr;
    				min = Math.min(min, dir[1]);
    				path[1] = "l"+directionsToHole[ro][co];
    			}
    		}
    		steps=0;
    		ro = ballRow;
    		co = ballColumn;
    		while(co<=cols-2){
    			if(ro == holeRow && co+1 == holeColumn){// hole found
    				steps++;
    				directionsToHole[ballRow][ballColumn] = "r";
    				maze[ballRow][ballColumn] = 0;
    				shortestDistanceToHole[ballRow][ballColumn] = steps;
    				return steps;
    			}
    			if(maze[ro][co+1]==0){
    				co++;
    				steps++;}
    			else break;
    		}
    		if(co>ballColumn && !(co<=cols-2 && maze[ro][co+1]==-2)){
    			tr = rollTheBall(maze,ro,co,holeRow,holeColumn);
    			if(tr>-1){
    				dir[2] = steps + tr;
    				min = Math.min(min, dir[2]);
    				path[2] = "r"+directionsToHole[ro][co];
    			}
    		}
    		steps=0;
    		ro = ballRow;
    		co = ballColumn;
    		while(ro>=1){
    			if(ro-1 == holeRow && co == holeColumn){ // hole found
    				steps++;
    				directionsToHole[ballRow][ballColumn] = "u";
    				maze[ballRow][ballColumn] = 0;
    				shortestDistanceToHole[ballRow][ballColumn] = steps;
    				return steps;
    			}
    			if(maze[ro-1][co]==0){
    				ro--;
    				steps++;
    			}
    			else break;
    		}
    		if(ro<ballRow && !(ro>=1 && maze[ro-1][co]==-2)){
    			tr = rollTheBall(maze,ro,co,holeRow,holeColumn);
    			if(tr>-1){
    				dir[3] = steps + tr;
    				min = Math.min(min, dir[3]);
    				path[3] = "u"+directionsToHole[ro][co];
    			}
    		}
    		
    		// if no path was found
    		if(min == Integer.MAX_VALUE){
    			maze[ballRow][ballColumn] = 0;
    			return -1;
    		}
    		
    		// the first of the entries which have the smallest path
    		for(int i=0;i<4;i++)
    			if(dir[i]==min){
    				directionsToHole[ballRow][ballColumn] = path[i];
    				maze[ballRow][ballColumn] = 0;
    				shortestDistanceToHole[ballRow][ballColumn] = dir[i];
    				return dir[i];
    			}
    		shortestDistanceToHole[ballRow][ballColumn] = -1;
    		return -1;
    	}
    }
    

  • 0
    A

    I have the same idea like you. And tried to make the code short
    https://discuss.leetcode.com/topic/77215/java-dfs-memoization-13ms-60lines


  • 0

    Thank you for that precise code. :)


Log in to reply
 

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