Directed mazes

Directed mazes are, like most mazes, traversed by moving from intersection to intersection until the goal intersection is reached. As each intersection is approached from a given direction, a sign near the entry to the intersection indicates in which directions the intersection can be exited. These directions are always left, forward, right, or any combination of these.

Figure 1 illustrates a directed maze. The intersections are identified as (row, column) pairs, with the upper left being (1, 1). The Entrance intersection for Figure 1 is (3, 1) and the Goal intersection is (3, 3). You begin the maze by moving north from (3, 1). As you walk from (3, 1) to (2, 1), the sign at (2, 1) indicates that as you approach (2, 1) from the south (traveling north) you may continue to go only forward. Continuing forward takes you toward (1, 1). The sign at (1, 1) as you approach from the south indicates that you may exit (1, 1) only by making a right turn. This turns you to the east, now walking from (1, 1) toward (1, 2). So far there have been no choices to be made. This is also the case as you continue to move from (1, 2) to (2, 2) to (2, 3) to (1, 3). Now, however, as you move west from (1, 3) toward (1, 2), you have the option of continuing straight on or turning left. Continuing straight on would take you toward (1, 1), while turning left would take you south to (2, 2). The actual (unique) solution to this maze visits the following sequence of intersections: (3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1) (2,2) (1,2) (1,3) (2,3) (3,3).

If you arrive at an intersection that has no sign for the direction in which you are traveling (for instance, when traveling south to (3, 1) in Figure 1), you have reached a dead end and may not proceed beyond that intersection.

You must write a program to solve valid directed mazes. Solving a maze means finding, if possible, a route through the maze that leaves the Entrance in the prescribed direction and ends at the Goal. This route should not be longer than necessary.

The input consists of one or more directed mazes. The first line of each maze description contains the name of the maze, which is an alphanumeric string of no more than 20 characters. The next line contains, in the following order, the starting row, the starting column, the starting direction, the goal row, and the goal column, all separated by a single space. The maximum dimensions of a maze are 9 by 9, so all row and column numbers are single digits from 1 to 9. The starting direction is one of the characters N, S, E, or W, indicating north, south, east, and west, respectively.

Each remaining line of a maze has this format: two integers, one or more groups of characters, and a sentinel asterisk (*), again all separated by a single space. The two integers are the row and the column of a maze intersection. Each character group describes one sign at that intersection. The first character of the group is N, S, E, or W and indicates the direction of travel for which the sign is seen; for example, S marks the sign seen when traveling south (the sign posted at the north entrance to the intersection). Following this first character are one to three arrow characters L, F, or R, meaning left, forward, and right, respectively.

The list of intersections for a maze is terminated by a line containing a single 0 in the first column. The next line begins the next maze, and so on. The end of the input is the word END on a line by itself.

For each maze, output a line containing the name of the maze, followed by a line containing either the maze's answer or the phrase No solution possible. The maze name must start in column 1, and the second line must start in column 3 (that is, indented by two spaces).

Among all routes that leave the Entrance in the prescribed direction and end at the Goal, the shortest route is the one that visits the fewest intersections (counting the Entrance and the Goal, and counting a repeated intersection each time it is visited). If the maze can be solved, print the number of intersections on this shortest route; otherwise print No solution possible.