Write a computer program to help a droid to navigate a maze of rooms. Your program will help the droid to find the shortest direct (no repeats) path from a start room to an ending room (a room with an exit) in the maze. The input will be a maze read from a text file. The file has the following structure
● The first line contains an integer represents the number of rooms in the maze
● The second line contains an integer represents the id of the starting room
● The third line contains an integer represents the id of the ending room (the room with the exist)
● The rest of the file contains the maze represented as a 2-dimensional square matrix. The row and column indices represent the room id. The data inside the matrix indicates if there is a door from one room to another room or not. For example, if maze[3][7] =1. This means there is a door from room 3 to room 7 and
if maze [4][1]= 0 this mean there no door from room 4 to room 1
For instance let us assume the following maze:
The input file for the maze above is shown on the next page
University of Windsor
School of Computer Science
Fall 2017
Input File
8
0
6
1,1,0,0,1,1,0,0
1,1,0,0,1,0,0,0
0,0,1,1,0,0,0,1
0,0,1,1,0,1,1,0
1,1,0,0,1,1,0,0
1,0,0,1,1,1,0,0
0,0,0,1,0,0,1,1
0,0,1,0,0,0,1,1
Output
0, 5, 3, 6
Note
1. Other paths such as [0, 1,4, 5,3, 6] or [0, 5, 3, 2, 7, 6] are not accepted since they are not shortest path
2. It is possible that the maze has no solution, for example, the dorid gets trapped in a cycle (loop). For example, given the following maze if the starting room is 3 and the end room is 2. The droid will get trapped in a cycle [3, 5, 4, 6, 3]. Your program should detect the case where there is no solution
