Clear java memorized dfs search solution, beats 80%


  • 0

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

Log in to reply
 

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