Tarzan was spending a peaceful day in the jungle when his friend Jojo the chimpanzee began taunting him. "You can't catch me, ape-man," shouted Jojo. Tarzan, always one to enjoy a good chase, began swinging after him, only to nd that Jojo had tangled up all of the hanging tree vines. Therefore, as Tarzan swings through the jungle, he can only move in the direction of the arrow in the square at the beginning of each swing. And because of the length of the vines, each swing must carry him exactly three or four squares.

Tarzan begins on the square at the top. From there he can travel three squares to A or go four squares to B. Suppose he goes to square B. On the next turn he can only go three squares (from B it is impossible to travel four squares). From square C he can go three squares to D or four squares to E.

Jojo has hidden in the square at the bottom of the maze of vines. How can Tarzan get to that square? (Note that only one square, the one marked F, will enable Tarzan to swing onto Jojo's square.

Implement your solution using Djikstra's algorithm in C++ or Java.

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 line contains two positive integers, s_r and s_c, representing the row and column at which Tarzan starts. (s_r will be in the range 1 to r, while s_c will be in the range 1 to c.)

The following r lines contain the directional information for each vine in the maze. Each line has c entries, where each integer represents one of three things: (1) the direction of the vine at that location ('N', 'E', 'S', 'W', 'NE', 'NW', 'SE', or 'SW'), (2) a location with no vine ('X'), or (3) the location of Jojo ('J').

For the original "Tarzan and Jojo" maze, the input is:

The maximum dimensions for a maze are 1000 by 1000.

Your program should write its output to the file output.txt, in the following format. The output should consist of a path from Tarzan's start location to Jojo. It should be a single line consisting of a sequence of moves, separated by spaces. Each move should be a string composed of two parts, separated by a hyphen (-). The first part should be the direction of the move (N, E, S, W, NE, NW, SE, or SW), and the second part should be the distance of the move (3 or 4). Beginning from Tarzan's start location, this sequence of moves must match the direction of every vine Tarzan swings from and end at Jojo, and it should not leave the maze or encounter a vine marked with an 'X'. If there are multiple valid paths through the vine maze, you may output any such path.

For example, if your first three moves take you 4 spaces south, 3 spaces south, and 3 spaces east, your output should begin with S-4 S-3 E-3.

FIT] RE ETIT EiriEET FIT] RE ETIT EiriEET