Please solve this question below and give me the code. Thanks

START t of ar- you solve this puzzle. You must find a- may then proceed to the bull's-eye and dess of route from the red arrow at the upper left escape from the maze. It's far more like- ht him to the bull's-eye at the lower right. The ly, though, that you will wander into aThis problem is based on the "Apollo and Diana" maze problem (from "MAD MAZES: Intriguing Mind Twisters for Puzzle Buffs, Game Nuts and Other Smart People" by Robert Abbott). The text of the problem is quoted below. A diagram of the maze appears on the next page. Apollo, god of the sun, stole a set of arrows from his sister Diana, goddess of the moon. When Diana caught him shooting moonbeams instead of sunbeams, she was furious! She cast a mighty curse, and all his arrows fell around him in a terrible maze. That maze is shown here. Apollo's sunbeams are the red arrows; Diana's moonbeams are the blue arrows. Diana spoke to Apollo: "You will remain here in this field of arrows until you solve this puzzle. You must find a route from the red arrow at the upper left to the bull's-eye at the lower right. The first red arrow points to two blue arrows. Choose either of those blue arrows and move to it. You are now on a blue arrow that points to one or more red arrows. Choose one of those red arrows. and move to it. Continue in this fashion, alternating between red and blue arrows. If you are truly wise you will arrive at an arrow that points to the bull's eye. You may then proceed to the bull's eye and escape from the maze. It's far more likely, though, that you will wander into a loop and find yourself going around endlessly. If that happens, you can admit that you are lost, go back to the red arrow at the upper left, and start the puzzle over again." So, how can Apollo find his way to the bull's eye (without getting stuck in too many loops)?3 Coding your solution In addition to the report, you should implement your algorithm in C or C+ + so that it can solve "Apollo and Diana" mazes. Your code may be in C or C+ +, but it must compile and run on the C4 Linux Lab machines. Your code may be split into any number of files. In addition, you are allowed to make use of any built-in library, and C+ + users may use the Boost library in their implementations. Boost is a free, open-source library with a rich collection of mathematical functions, including several that deal with graphs. You may read more about Boost at www. boost . org and the Boost Graph Library at https://www. boost . org/doc/libs/1_82_0/libs/graph/doc/index. html. 3.1 Input format Your program should read its input from the file input. txt, in the following format. The input begins with a two positive integers on a line indicating the number of rows r and columns c of the maze, respectively. The next r lines contain the color and directional information for each arrow in the maze. Each line has c values, where each value represents the color of the arrow in the corresponding row and column in the maze (R or B), followed by a hyphen (-), followed by the direction of the arrow (N, E, S, W, NE, SE, SW, or NW). The color codes R and B represent "red" and "blue," respectively, while the direction codes N, E, S, W, NE, SE, SW, and NW represent "north," "east," "south," "west," "northeast," "southeast," "southwest," and "northwest," respectively. The goal square (bulls-eye) is represented by a letter O. You may assume that the bulls-eye will always be in the bottom-right corner of the maze. For the "Apollo and Diana" maze, the input is: 8 8 R-E R-SE B-S B-SW R-S R-SW R-S R-S B-E R-S B-SE R-E B-SE B-S B-W R-SW R-N B-W B-SW R-SE R-NE B-SW B-W R-W R-SE R-SE B-SW R-SE R-S B-NW R-E B-NW B-NE R-W R-S B-S B-E B-NE B-NW R-NW R-S B-SE R-SE R-SE R-NW R-NE B-E R-W R-NE B-W B-SE R-E R-E B-E B-NW R-SW B-NE R-E B-N R-NE B-NE B-N B-NW 3 3.2 Output format Your program should write its output to the file output . txt, in the following format. The output should consist of a path from the top left square to the bottom right square (bulls-eye). It should be a single line consisting of a sequence of moves, separated by spaces. Each move should be represented by the number of spaces to move and the direction, with no space in between. The direction should be represented using N, E, S, W, NE, SE, SW, and NW, as in the input. Of course, the sequence of moves described in the file must solve the maze described in the input. For example, if your first three moves take you 3 spaces east, 3 spaces southwest, and 4 spaces southeast, your output should begin as follows: 3E 3SW 4SE You are welcome to try figuring out the solution to the "Apollo and Diana" puzzle on your own, but that won't get you any points. Your assignment is to model the maze as a graph and to solve the problem using an appropriate graph algorithm. 4 Submission You must submit a zip archive containing 1) your report (described in Section ??) as a PDF document, 2) your code (described in Section ??), and 3) a README file describing how to compile and run your code to Canvas. If your code requires more than a simple command to compile and run then you must also provide a Makefile and/or shell script. A simple command might be something like: gcc *. c -o maze or g++ *. cpp -o maze If you are using Boost in your solution, you must provide a Makefile and/or shell script that uses the environment variable $BOOST_HOME (pointing to the Boost installation directory) to compile your code