Java || 👍Explained in Detail👍|| Simple & Fast Solution✅|| BFS
I do my best everyday to give a clear explanation, so to help everyone improve their skills.\n\nIf you find this helpful, please \uD83D\uDC4D upvote this post a
I do my best everyday to give a clear explanation, so to help everyone improve their skills.\n\nIf you find this **helpful**, please \uD83D\uDC4D **upvote** this post and watch my [Github Repository](https://github.com/cheehwatang/leetcode-java).\n\nThank you for reading! \uD83D\uDE04 Comment if you have any questions or feedback.\n\n---\n\n## Approach\nA classic breadth first search problem, we use slowly expanding from the starting node.\n\nWe can imagine every position in the \'maze\' as a node with the \'maze\' being a directional graph, since we cannot visit the same node twice to find the shortest path to the exit.\n\nAs such, we take one step at a time to all directions to a new valid position.\n\nNote to check for invalid moves, either that direction is out of bound or towards a wall.\n\nIf that direction leads to a border space, it means it is the exit.\nWith breadth first search, we use Queue store the nodes for the next step.\n\nTo mark the visited node, we can either use an additional 2D boolean array to record, or mark the visited node as a wall \'+\' in \'maze\', latter which is implemented here.\n\n## Complexity\nTime Complexity  : O(m * n),\nwhere \'m\' is the number of rows, and \'n\' is the number of columns.\nWith the worst case being that we check every position in the \'maze\'.\n\nSpace Complexity : O(m + n),\nwhere \'m\' is the number of rows, and \'n\' is the number of columns.\nThe queue grows linearly with the rows and columns of the matrix, as we are constantly removing nodes from the queue at each step, with the max queue size being the distance from the center to the edge of the \'maze\'.\n\nIf we use a 2D boolean array for the visited nodes, then the space complexity is O(m * n).\n\n---\n### Java - With Explanation\n```\nclass Solution {\n    public int nearestExit(char[][] maze, int[] entrance) {\n        int rows = maze.length;\n        int columns = maze[0].length;\n\n        // For breadth first search, offer the first node (\'entrance\').\n        // Note that we immediately mark the node as visited when putting into the queue as to\n        // prevent other nodes from visiting it. Otherwise, we will be trapped in an infinite loop.\n        // Credit: @b_clodius for the detailed explanation and test.\n        Queue<int[]> queue = new LinkedList<>();\n        queue.offer(entrance);\n        maze[entrance[0]][entrance[1]] = \'+\';\n\n        // As simple 2D array to keep track of the directions to take.\n        // We can use 4 separate operation, but it is more efficient to use a for-loop to go through the four directions.\n        int[][] directions = new int[][] {{0,1},{0,-1},{1,0},{-1,0}};\n\n        int steps = 0;\n        int x, y;\n        while (!queue.isEmpty()) {\n            // We take a step before checking the directions for the nodes that we are at (in the queue).\n            steps++;\n\n            // Make sure to use a variable to keep track of the queue.size(),\n            // because the queue size continuously changes as we check for the other nodes,\n            // which can lead to infinite loops or undue termination of the for-loop.\n            int n = queue.size();\n\n            // Check every node at the current step.\n            for (int i = 0; i < n; i++) {\n                int[] current = queue.poll();\n                // For each node, check every direction.\n                for (int[] direction : directions) {\n                    x = current[0] + direction[0];\n                    y = current[1] + direction[1];\n\n                    // Check if this direction out of bound.\n                    if (x < 0 || x >= rows || y < 0 || y >= columns) continue;\n                    // Check if this direction is the wall.\n                    if (maze[x][y] == \'+\') continue;\n\n                    // If this direction is empty, not visited and is at the boundary, we have arrived at the exit.\n                    if (x == 0 || x == rows - 1 || y == 0 || y == columns - 1) return steps;\n\n                    // Otherwise, we change this direction as visited and put into the queue to check at the next step.\n                    maze[x][y] = \'+\';\n                    queue.offer(new int[]{x, y});\n                }\n            }\n\n        }\n        // If all the possible nodes and directions checked but no exits found, return -1.\n        return -1;\n    }\n}\n```\n\n### Java - Clean Code\n```\nclass Solution {\n    public int nearestExit(char[][] maze, int[] entrance) {\n        int rows = maze.length;\n        int columns = maze[0].length;\n\n        Queue<int[]> queue = new LinkedList<>();\n        queue.offer(entrance);\n        maze[entrance[0]][entrance[1]] = \'+\';\n\n        int[][] directions = new int[][] {{0,1},{0,-1},{1,0},{-1,0}};\n\n        int steps = 0;\n        int x, y;\n        while (!queue.isEmpty()) {\n            steps++;\n\n            int n = queue.size();\n            for (int i = 0; i < n; i++) {\n                int[] current = queue.poll();\n\n                for (int[] direction : directions) {\n                    x = current[0] + direction[0];\n                    y = current[1] + direction[1];\n\n                    if (x < 0 || x >= rows || y < 0 || y >= columns) continue;\n                    if (maze[x][y] == \'+\') continue;\n\n                    if (x == 0 || x == rows - 1 || y == 0 || y == columns - 1) return steps;\n\n                    maze[x][y] = \'+\';\n                    queue.offer(new int[]{x, y});\n                }\n            }\n        }\n        return -1;\n    }\n}\n```
['Array', 'Breadth-First Search', 'Matrix', 'Java']