Clear java memorized dfs search solution, beats 80%

• The idea for this problem is that you need to move several steps until meet borders or wall or a hole instead of moving one step like other similar problems. Also, we only care about the point that we will stop and memorize the shortest distance from start point there

``````public class Solution {
public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
if(maze==null||maze.length==0||maze[0]==null||maze[0].length==0){
return "impossible";
}
int m=maze.length, n=maze[0].length;
int[][] mem=new int[m][n];
for(int[] row:mem){
Arrays.fill(row, Integer.MAX_VALUE);
}
//set hole
maze[hole[0]][hole[1]]=-1;
Search(ball[0], ball[1], m, n, 0, "", maze, mem);
return this.res==null?"impossible":this.res;
}
private void Search(int i, int j, int m, int n, int d, String cur, int[][] maze, int[][] mem){
//if current distance to this point is larger, we don't need to explore further
if(d>min||d>mem[i][j]){
return;
}
//memorize minimum distance to here
mem[i][j]=Math.min(mem[i][j], d);
//If find meet a hole
if(maze[i][j]==-1){
if(d<this.min){
this.min=d;
this.res=cur;
}
else if(d==this.min&&cur.compareTo(this.res)<0){
this.res=cur;
}
}
//for four directions
for(int k=0;k<4;k++){
//don't turn back
if(!cur.isEmpty()){
char c=cur.charAt(cur.length()-1);
if(k==0&&c=='u'||k==1&&c=='d'||k==2&&c=='l'||k==3&&c=='r'){
continue;
}
}
int[] dir=this.directions[k];
int it=i, jt=j;
//roll to one direction until meet border, wall or a hole
while(check(it+dir[0], jt+dir[1], m, n)&&maze[it+dir[0]][jt+dir[1]]!=1&&maze[it][jt]!=-1){
it+=dir[0];
jt+=dir[1];
}
//if position changed
if(it!=i||jt!=j){
Search(it, jt, m, n, d+Math.abs(it-i)+Math.abs(jt-j), cur+symbol[k], maze, mem);
}
}
}
//check if a point is into border
private boolean check(int i, int j, int m, int n){
if(i>=0&&i<m&&j>=0&&j<n){
return true;
}
else{
return false;
}
}
private int[][] directions={{1,0},{-1,0},{0,1},{0,-1}};
private String[] symbol={"d", "u", "r", "l"};
private int min=Integer.MAX_VALUE;
private String res;
}
``````

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