An analysis on Time Limit Exceeded (TLE)
If you are facing TLE you probably made the same mistake as me.\n\nCorrect Way: When pushing a coordinate to the queue immediately mark it + or add it to your v
If you are facing TLE you probably made the same mistake as me.\n\n**Correct Way**: When pushing a coordinate to the queue immediately mark it ```+``` or add it to your visited hashset.\n\n```\n            for path in range(size):\n                row, col = queue.popleft()\n                if moves > 0 and (row == len(maze) - 1 or row == 0 or col == 0 or col == len(maze[row]) - 1):\n                    return moves\n\n                if row + 1 < len(maze) and maze[row + 1][col] == ".":\n                    queue.append((row + 1, col))\n                    maze[row + 1][col] = "+" #  Important\n                if row - 1 >= 0 and maze[row - 1][col] == ".":\n                    queue.append((row - 1, col))\n                    maze[row - 1][col] = "+" #  Important\n                if col + 1 < len(maze[row]) and maze[row][col + 1] == ".":\n                    queue.append((row, col + 1))\n                    maze[row][col + 1] = "+" #  Important\n                if col - 1 >= 0 and maze[row][col - 1] == ".":\n                    queue.append((row, col - 1))\n                    maze[row][col - 1] = "+" #  Important\n            moves += 1\n```\n\n**Incorrect Way**: Mark ```+``` or add to visited hashset after popping from queue.  If we implement this way we mistakenly add many duplicate coordinates to the queue.\n\n```\n            for path in range(size):\n                row, col = queue.popleft()\n                maze[row][col] = "+"  #  Wrong\n                if moves > 0 and (row == len(maze) - 1 or row == 0 or col == 0 or col == len(maze[row]) - 1):\n                    return moves\n\n                if row + 1 < len(maze) and maze[row + 1][col] == ".":\n                    queue.append((row + 1, col))\n                if row - 1 >= 0 and maze[row - 1][col] == ".":\n                    queue.append((row - 1, col))\n                if col + 1 < len(maze[row]) and maze[row][col + 1] == ".":\n                    queue.append((row, col + 1))\n                if col - 1 >= 0 and maze[row][col - 1] == ".":\n                    queue.append((row, col - 1))\n            moves += 1\n```\n\nFascinated by this mistake I decided to profile the mistake using a large test case that gave me my original TLE.  This test case used a 100 x 100 graph with all edges being blocked by ```+``` except one exit on the first row and an entrance of ```[82,19]```.  All points inside edges are ```.```. For this particular test case the optimal result requires 131 moves.\n\nWith an incorrect implementation we not only have horrible runtime but we eventually run out of memory.  My machine was at 12.97 GB after a few minutes before I had to force kill it.\n\n```\nQueue Unique Size | Queue Total Size | Total Moves in\n4 4 1\n8 12 2\n12 28 3\n16 60 4\n20 124 5\n24 252 6\n28 508 7\n32 1020 8\n36 2044 9\n40 4092 10\n44 8188 11\n48 16380 12\n52 32764 13\n56 65532 14\n60 131068 15\n64 262140 16\n67 524283 17\n69 1048535 18\n70 2096766 19\n```\n
[]