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

• 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;
}
}
``````

• 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

• Thank you for that precise code. :)

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