A seemingly straightforward task such as driving cargo from point A to point B can sometimes be very tricky! GPS systems can be very helpful for finding routes, but usually don’t take all things into consideration. For instance, when finding the quickest route, do they consider waiting at traffic lights? What about congestion? Maybe you can write superior software? In this problem, you will be given a street map containing roads, numbered intersections (with traffic lights), and two warehouses. Your task is to find the fastest route to drive a truck from warehouse A to warehouse B. Street maps are always drawn on a grid, and look like this:

      #A##0##1#
      .#..#..#.
      .#..#..#.
      .###2#.B.
Figure 2: A street map with warehouses, roads, and intersections.

Adjacency on this map is defined as neighboring north, south, east, or west. The only symbols that appear on the map are the following: • A # character indicates a road cell that trucks can drive on. Roads are adjacent to at most two other road, intersection, or warehouse cells. • A single number [0-9] marks an intersection controlled by a traffic light. Intersections are adjacent to at least three road cells. Intersections are uniquely numbered sequentially: no number will appear unless all nonnegative integers less than it also appear on the map. The behavior of traffic lights will be described below. • Exactly one character A marks the location of the warehouse where your trucks start. • Exactly one character B marks the location of the warehouse where you’d like to ship your cargo to. • A . character is just grass. You cannot drive on these. You have one cargo truck that starts at warehouse A, and you are trying to drive it to warehouse B according to the rules below. For simplicity, we can also discretize time into atomic units, or turns. • On a single turn, you may move the truck onto an adjacent road, intersection, or warehouse cell, or simply remain in the same cell. • A truck may only move into an intersection cell if the traffic light for the intersection is green in the direction the truck is entering from during that turn. However, a truck on an intersection cell can exit in any direction at any time. Intersections with traffic lights periodically allow either east-west or north-south traffic flow, but not both at the same time. They are described by an initial direction and two numbers indicating the east-west and north-south periods, respectively. For example, an intersection initially green on the north-south direction described by “2 3” will have a green light facing north and south on turns 1-3 inclusive, facing east and west on turns 4-5, and again north and south on turns 6-8, etc.

The input test file will contain multiple cases. Each test case begins with a single line containing two integers, m and n, separated by spaces. The street map consists of m rows (east-west) and n columns (north-south) of grid cells (2 ≤ m, n ≤ 20). The next m lines contain n characters each, which describe the map using the symbols defined in the problem statement above. For each numbered intersection that appears in the map, in ascending order beginning with 0, there will be a line of text with the intersection number followed by either a ‘-’ or ‘|’pharacter and two integers, ai and bi (1 ≤ ai, bi ≤ 100), the duration (in turns) of the east-west and north-south periods of the light, respectively. A ‘-’ indicates that the traffic light is initially green in the east-west direction, while a ‘|’ indicates that it is initially green in the north-south direction. A blank line separates input test cases, as seen in the sample input below. A single line with the numbers “0 0” marks the end of input; do not process this case.

For each test case, your program should print one integer on a single line: the minimum number of turns it takes to drive your truck from warehouse A to warehouse B. If it is not possible to get to warehouse B, print a single word “impossible”. Output corresponding to the sample input would appear as such:

(In the second example, it is actually quicker to take the bottom route than the top. However, your truck must wait west at intersection 2 until it can enter on turn 7, when the light is green, and then reaches intersection 0 on turn 10, wait again west of intersection 1 until turn 14, and finally enters warehouse B at the end of turn 17).

2008 Stanford Local Programming Contest