*I updated to include which direction we can move after the prerequisites.

Scenario

Our maze is an H by W rectangle, represented by an array of size H of W-sized strings. Each character in a string can either be '#' or '.'. '#' represents a wall, which we cannot cross, and '.' represents a free space, which we can cross. The border of the maze is always filled with '#' except for one square, which represents the exit. For example, the following is a valid maze:

Find the total number of steps to exit the maze, when supplied with a starting point (i,j) (with (0, 0) being the upper-left point and (H, W) being the lower-right point).

Aim: Use BFS to find the shortest path out of a given maze.

Prerequisites: Implement the distToExit() method of the Maze class in the source code, which returns the integer distance from that point to the exit of the maze.

Assume that the points supplied to distToExit() are valid (that is, they're not inside walls). Remember that we can only move in the cardinal directions (North, South, East, and West).

public int distToExit(int i, int j) { return -1; }

Steps for Completion

1. Encode the maze representation to a graph representation.
2. Apply the BFS implementation shown in the preceding lesson (with a small modification to account for distances), or you can build the graph as you go.
3. Since you know that there are at most four outward edges for a given vertex, compute their positions as you go.

Grading

Complete each task listed below. Each task contains automated checks which are used to calculate your grade. When you have completed each task by clicking the checkbox, open the task list panel on the left navigation bar and click the "Submit" button.

Task: Implemented the distToExit() method using BFS.

Here is the code we are given to complete in JAVA, there is a section towards the end where we are to write our code:

public class Maze { private int H; private int W; private int exitI; private int exitJ; private String[] maze;

public Maze(String[] maze) { this.maze = maze; this.H = maze.length; this.W = maze[0].length(); for (int i = 0; i

public int distToExit(int i, int j) { // Write your code here return -1; } }

##.## #... #,#, #,# , # #.###.# #,,,,, #######