My dfs code only passes 80% of test cases. Can anyone point out the logic error?


  • 0
    B

    '''
    public class Solution {
    final int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
    //remap walls as -1
    for(int i=0;i<maze.length;i++){
    for(int j=0;j<maze[0].length;j++)
    if(maze[i][j]==1) maze[i][j]=-1;
    }
    //do a dfs
    int min = dfs(maze, start[0], start[1], destination);
    return min==Integer.MAX_VALUE?-1:min;
    }

    public int dfs(int[][] maze, int row, int col, int[] dest){
        if(row==dest[0]&&col==dest[1])
            return 0;
        //ive visted here before so return
        if(maze[row][col]>0)
            return maze[row][col];
        int thisMin = Integer.MAX_VALUE;
        //mark here as visited
        maze[row][col] = Integer.MAX_VALUE;
        for(int[] dir:dirs){
            int r = row;
            int c = col;
            int length = 0;
            while(!(r<0||r>=maze.length||c<0||c>=maze[0].length)&&(maze[r][c]>=0)){
                length++;
                r+=dir[0];
                c+=dir[1];
            }
            r-=dir[0];
            c-=dir[1];
            length--;
            int thisPath = dfs(maze, r, c, dest);
            if(thisPath!=Integer.MAX_VALUE)
                thisMin = Math.min(thisMin, thisPath+length);
        }
        maze[row][col] = thisMin;
        //System.out.println(row+","+col+"  "+thisMin);
        return thisMin;
    }
    

    }
    '''


Log in to reply
 

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