Challenge: Escape the Maze

Lab Java Intermediate 20 points

A maze is a grid: S start, E exit, # wall, . open floor. Moving up, down, left or right takes one step. Print the fewest steps from S to E, or -1 if there's no way out. Use BFS on the grid.

Input

Line 1: rows cols. Then rows lines of the maze.

Output

The fewest steps, or -1.

Example

Input

3 4
S.#.
.##.
...E

Output

Sample input available Sample output available

Editor

Java

Hints

Find S while reading the grid and start BFS there.

Use dr = {-1, 1, 0, 0} and dc = {0, 0, -1, 1} for the four moves. Skip walls, cells off the grid and seen cells.

Solution explanation

Each cell is visited at most once: O(rows × cols).

Show solution

import java.util.ArrayDeque;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int rows = sc.nextInt(), cols = sc.nextInt();
        char[][] maze = new char[rows][];
        int[][] dist = new int[rows][cols];
        ArrayDeque<int[]> queue = new ArrayDeque<int[]>();
        for (int r = 0; r < rows; r++) {
            maze[r] = sc.next().toCharArray();
            for (int c = 0; c < cols; c++) {
                dist[r][c] = -1;
                if (maze[r][c] == 'S') {
                    dist[r][c] = 0;
                    queue.offer(new int[]{r, c});
                }
            }
        }
        int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            if (maze[cell[0]][cell[1]] == 'E') {
                System.out.println(dist[cell[0]][cell[1]]);
                return;
            }
            for (int d = 0; d < 4; d++) {
                int r = cell[0] + dr[d], c = cell[1] + dc[d];
                if (r < 0 || c < 0 || r >= rows || c >= cols) continue;
                if (maze[r][c] == '#' || dist[r][c] != -1) continue;
                dist[r][c] = dist[cell[0]][cell[1]] + 1;
                queue.offer(new int[]{r, c});
            }
        }
        System.out.println(-1);
    }
}

Output

Answer