[Solved] COMP2540 Assignment4 droid to navigate a maze of rooms

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