CODE IN C++ BELOW IS SAMPLE INPUT AND SOLUTION TO CHECK

INPUT:

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 O

OUTPUT:

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 wont get you any points. Your assignment is to model the maze as a graph and to solve the problem using an appropriate graph algorithm

SAMPLE SOLUTION:

2E 4S 2S 1SE 3NE 3NW 3E 5W 1S 1W 1N 7E 1SW 3W 2SE 2NE 5W 1SW 4SE 7N 3SW

2SW 2S 7NE 7S