4. Game (25%) Write a program to reach the end point in a maze using following coordinates. The coordinates of the 25 cells in a maze 0001 02 03 04 10 11 12 13 14 20 21 22 23 24 30 31 32 33 34 40 41 42 43 44 Part (a): Please implement the game according to the following requirements: We can present the coordinates of each cell using (x, y) with x and y two values, where x and y are for the row and column index values, respectively. The program always starts from the cell (0,0) and visits different cells to reach the end point ('x'). We draw an 'o' (letter 'o' not number zero) for each cell that has been visited. We assume that the end point ('x') is NOT in the first row and is also NOT in the first column. There is one and only one obstacle (**'), which is NOT at the cell (0,0) and NOT at the end point. We assume that the obstacle is NOT in the first row and is also NOT in the first column. Start from (0,0) and move one step each time based on user's input (i.e. up, down, left, right or hint). When the input is one of up, down, left, or right (hint is handled in part b), If this input leads to an empty cell (-), move to this cell and draw a footprint ('o') in this cell. o If this input leads to a position 1) outside the maze, 2) that has been visited before, or 3) with the obstacle, output an error message and then let the player to input again. o If this input leads to the end point, the game is finished with a Successful!" message. Note 1: We assume the user's input is valid. No need to check the input's correctness. Note 2: You do not need to consider the case that there is no cell to move but the game is not ended yet. Example-1: Example-2: Initial maze: Initial maze: o - Input an integer (1:up 2:down 3:left 4:right 5:hint): 4 Input an integer (1:up 2:down 3:left 4:right 5:hint): 4 1 1 * O 1 Input an integer (1:up 2:down 3:left 4:right 5:hint): 4 ITO Input an integer (1:up 2:down 3:left 4:right 5:hint): 2 There is an obstacle! Input an integer (1:up 2:down 3:left 4:right 5:hint): 4 Input an integer (1:up 2:down 3:left 4:right 5:hint): 1 Outside the maze! Input an integer (1:up 2:down 3:left 4:right 5:hint): 3 You have visited this cell before! Input an integer (1:up 2:down 3:left 4:right 5:hint): 2 Input an integer (1:up 2:down 3:left 4:right 5:hint): 2 O 01 - Successful! Successful! Part (b): Continue working on your solution to part a) to handle the case when the input is 5 for hint. When the input is 5, each cell is changed to its original value in the initial maze, and then the program displays a shortest path (in terms of the number of cells) from the cell (0,0) to the end point. The movements along this shortest path satisfy the requirements in Part (a). If there are multiple shortest paths, just display any one of them. Example-3: Example-4: Initial maze: Initial maze: - Input an integer (1:up 2:down 3:left 4:right 5:hint): 4 Input an integer (1 :up 2:down 3:left 4:right 5:hint): 4 110 OLIO - - - Input an integer (1:up 2:down 3:left 4:right 5:hint): 2 Input an integer (1:up 2:down 3:left 4:right 5:hint): 5 o - Input an integer (1:up 2:down 3:left 4:right 5:hint): 2 Successful! Booo - - Input an integer (1:up 2:down 3:left 4:right 5:hint): 5 LITO - - Successful