C | 105ms(100%) & 7.4MB(100%) | BFS & Link list
Intuition\n Describe your first thoughts on how to solve this problem. \nUsing BFS by link list\n# Approach\n Describe your approach to solving the problem. \n1
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUsing BFS by link list\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Start from entrance and add link list\n2. Find next empty cells, \'.\', until the exit\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nstruct MazeRecord\n{\n    char cRow;\n    char cCol;\n    short sDistance;\n\n    struct MazeRecord* pstNext;\n};\n\nstruct MazeRecord* AddMazeRecord(struct MazeRecord* pstTail, char cRow, char cCol, short sDistance)\n{\n    if(pstTail->pstNext)\n    {\n        pstTail = pstTail->pstNext;\n    }\n    else\n    {\n        pstTail->pstNext = (struct MazeRecord*) malloc(sizeof(struct MazeRecord));\n        pstTail = pstTail->pstNext;\n        pstTail->pstNext = NULL;;\n    }\n\n    pstTail->cRow = cRow;\n    pstTail->cCol = cCol;\n    pstTail->sDistance = sDistance;\n\n    return pstTail;\n}\n\nint nearestExit(char** maze, int mazeSize, int* mazeColSize, int* entrance, int entranceSize){\n    char cMazeSize = mazeSize - 1, cMazeColSize = *mazeColSize - 1;\n\n    struct MazeRecord* pstHead = (struct MazeRecord*) malloc(sizeof(struct MazeRecord));\n    pstHead->cRow = *entrance;\n    pstHead->cCol = *(entrance + 1);\n    pstHead->sDistance = 0;\n    pstHead->pstNext = NULL;\n    maze[pstHead->cRow][pstHead->cCol] = \',\';\n\n    short sRet = 0;\n    struct MazeRecord* pstTail = pstHead;\n    while(pstHead)\n    {\n        // check up\n        if(pstHead->cRow && maze[pstHead->cRow-1][pstHead->cCol] == \'.\')\n        {\n            if(pstHead->cRow-1 == 0 || pstHead->cCol == 0 || pstHead->cCol == cMazeColSize)\n            {\n                sRet = pstHead->sDistance + 1;\n                break;\n            }\n            else\n            {\n                maze[pstHead->cRow-1][pstHead->cCol] = \',\';\n                pstTail = AddMazeRecord(pstTail, pstHead->cRow-1, pstHead->cCol, pstHead->sDistance+1);\n            }\n        }\n\n        // check left\n        if(pstHead->cCol && maze[pstHead->cRow][pstHead->cCol-1] == \'.\')\n        {\n            if(pstHead->cCol-1 == 0 || pstHead->cRow == 0 || pstHead->cRow == cMazeSize)\n            {\n                sRet = pstHead->sDistance + 1;\n                break;\n            }\n            else\n            {\n                maze[pstHead->cRow][pstHead->cCol-1] = \',\';\n                pstTail = AddMazeRecord(pstTail, pstHead->cRow, pstHead->cCol-1, pstHead->sDistance+1);\n            }\n        }\n\n        // check right\n        if(pstHead->cCol < cMazeColSize && maze[pstHead->cRow][pstHead->cCol+1] == \'.\')\n        {\n            if(pstHead->cCol+1 == cMazeColSize || pstHead->cRow == 0 || pstHead->cRow == cMazeSize)\n            {\n                sRet = pstHead->sDistance + 1;\n                break;\n            }\n            else\n            {\n                maze[pstHead->cRow][pstHead->cCol+1] = \',\';\n                pstTail = AddMazeRecord(pstTail, pstHead->cRow, pstHead->cCol+1, pstHead->sDistance+1);\n            }\n        }\n\n        // check down\n        if(pstHead->cRow < cMazeSize && maze[pstHead->cRow+1][pstHead->cCol] == \'.\')\n        {\n            if(pstHead->cRow+1 == cMazeSize || pstHead->cCol == 0 || pstHead->cCol == cMazeColSize)\n            {\n                sRet = pstHead->sDistance + 1;\n                break;\n            }\n            else\n            {\n                maze[pstHead->cRow+1][pstHead->cCol] = \',\';\n                pstTail = AddMazeRecord(pstTail, pstHead->cRow+1, pstHead->cCol, pstHead->sDistance+1);\n            }\n        }\n\n        if(pstHead == pstTail) break;\n\n        struct MazeRecord* pstTmp = pstHead;\n        pstHead = pstHead->pstNext;\n        pstTmp->pstNext = pstTail->pstNext;\n        pstTail->pstNext = pstTmp;\n    }\n\n    while(pstHead)\n    {\n        pstTail = pstHead;\n        pstHead = pstHead->pstNext;\n        free(pstTail);\n    }\n\n    return sRet? sRet: -1;\n}\n```
['C']