[C] DFS solution beats 100% c solutions


  • 0
    R
    #define VISITED 1
    #define NOT_VISITED 0
    
    typedef enum{
        left,
        right,
        up,
        down,
        invalid
    }direction_e;
    
    bool isWall(int** maze, int mazeRowSize, int mazeColSize, int sRow, int sCol){
        if(sRow < 0 || sRow >= mazeRowSize){
            return true;
        }
        
        else if(sCol < 0 || sCol >= mazeColSize){
            return true;
        }
        
        return maze[sRow][sCol];
    }
    
    bool isVisited(int** visit, int sRow, int sCol){
        return visit[sRow][sCol];
    }
    
    bool isDestination(int sRow, int sCol, int dRow, int dCol){
        return ((sRow == dRow) && (sCol == dCol));
    }
    
    bool isNextWall(int** maze, int mazeRowSize, int mazeColSize, int sRow, int sCol, int currDir){
        
        //printf("currDir: %d\n", currDir);
        
        if(currDir == left){
            sCol = sCol - 1;
        } 
        else if(currDir == right){
            sCol = sCol + 1;
        }
        else if(currDir == up){
            sRow = sRow - 1;
        }
        else if(currDir == down){
            sRow = sRow + 1;
        }
        
        return isWall(maze, mazeRowSize, mazeColSize, sRow, sCol);
    }
    
    bool hasPathHelper(int ** maze, int mazeRowSize, int mazeColSize, 
                       int sRow, int sCol, 
                       int dRow, int dCol, 
                       int** visit, int* currDir){
        
        bool isNodeWall = false;
        bool isNodeVisited = false;
        bool result = false;
        bool isNodeDest = false;
        bool isNextNodeWall = false;
        int prevRow;
        int prevCol;
        
        isNodeWall = isWall(maze, mazeRowSize, mazeColSize, sRow, sCol);
        if(isNodeWall){
            return false;
        }
        
        isNodeVisited = isVisited(visit, sRow, sCol);
        if(isNodeVisited){
            return false;
        }
        
        isNodeDest = isDestination(sRow, sCol, dRow, dCol);
        isNextNodeWall = isNextWall(maze, mazeRowSize, mazeColSize, sRow, sCol, *currDir);
        if(isNodeDest){
            if(isNextNodeWall){
                return true;
            }
        }
        
        if(*currDir < invalid && isNextNodeWall){
            *currDir = invalid;
        }
    
        prevRow = sRow;
        prevCol = sCol;
    
        if(*currDir == invalid){
    
            visit[sRow][sCol] = VISITED; // mark visited
            *currDir = left;
            result = hasPathHelper(maze, mazeRowSize, mazeColSize, sRow, sCol - 1, dRow, dCol, visit, currDir);  // Check left
    
            if(!result){
                *currDir = right;
                result = hasPathHelper(maze, mazeRowSize, mazeColSize, sRow, sCol + 1, dRow, dCol, visit, currDir);  // check right    
            }
    
            if(!result){
                *currDir = up;
                result = hasPathHelper(maze, mazeRowSize, mazeColSize, sRow - 1, sCol, dRow, dCol, visit, currDir);  // check up    
            }
    
            if(!result){
                *currDir = down;
                result = hasPathHelper(maze, mazeRowSize, mazeColSize, sRow + 1, sCol, dRow, dCol, visit, currDir);  // check down    
            }
        }
        else{
    
            prevRow = sRow;
            prevCol = sCol;
    
            if(*currDir == left){
                sCol = sCol - 1;
            } 
            else if(*currDir == right){
                sCol = sCol + 1;
            }
            else if(*currDir == up){
                sRow = sRow - 1;
            }
            else if(*currDir == down){
                sRow = sRow + 1;
            }
    
            result = hasPathHelper(maze, mazeRowSize, mazeColSize, sRow, sCol, dRow, dCol, visit, currDir);
        }
            
        return result;    
    }
    
    bool hasPath(int** maze, int mazeRowSize, int mazeColSize, 
                 int* start, int startSize, 
                 int* destination, int destinationSize) {
        int sRow = start[0];
        int sCol = start[1];
        int dRow = destination[0];
        int dCol = destination[1];
        int currDir = invalid;
        bool isPathExist = false;
        int** visit = NULL;
        
        visit = (int** )malloc(sizeof(int *) * mazeRowSize);
        for(int i = 0; i < mazeRowSize; i++){
            visit[i] = (int *)malloc(sizeof(int) * mazeColSize);
        }
        
        for(int i = 0; i < mazeRowSize; i++){
            memset(visit[i], (int)NOT_VISITED, sizeof(int) * mazeColSize);
        }
        
        isPathExist = hasPathHelper(maze, mazeRowSize, mazeColSize, sRow, sCol, dRow, dCol, visit, &currDir);
        
        return isPathExist;
    }
    

Log in to reply
 

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