Shortest Path in a Grid

Lab Java Advanced 30 points

Read a grid with S, E, . and #. Print the length of the shortest path from S to E (4 directions), or -1, using BFS with an ArrayDeque.

Input

r c, then r rows.

Output

One integer.

Example

Input

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

Output

Sample input available Sample output available

Editor

Java

Hints

BFS visits cells in order of distance from S.

Mark a cell's distance when you add it to the queue.

Solution explanation

BFS gives shortest paths in unweighted graphs; a grid is a graph of neighbouring cells.

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 r = sc.nextInt(), c = sc.nextInt();
        char[][] g = new char[r][];
        int[][] dist = new int[r][c];
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < r; i++) {
            g[i] = sc.next().toCharArray();
            for (int j = 0; j < c; j++) {
                dist[i][j] = -1;
                if (g[i][j] == 'S') {
                    dist[i][j] = 0;
                    queue.add(new int[]{i, j});
                }
            }
        }
        int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
        int answer = -1;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            if (g[cur[0]][cur[1]] == 'E') {
                answer = dist[cur[0]][cur[1]];
                break;
            }
            for (int d = 0; d < 4; d++) {
                int ni = cur[0] + dr[d], nj = cur[1] + dc[d];
                if (ni >= 0 && ni < r && nj >= 0 && nj < c && g[ni][nj] != '#' && dist[ni][nj] < 0) {
                    dist[ni][nj] = dist[cur[0]][cur[1]] + 1;
                    queue.add(new int[]{ni, nj});
                }
            }
        }
        System.out.println(answer);
    }
}

Output

Answer