Cargo Carriage#302
A seemingly simple task, such as transporting cargo from point to point , can sometimes be very complicated. GPS systems can be helpful for finding routes, but they do not always consider all factors. For example, do they take into account waiting at traffic lights when finding the fastest route? What about traffic jams? Maybe you can write better software?
In this problem, you are 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 to warehouse .
The street map is always drawn on a grid. Adjacency on the map is defined as neighboring cells to the north, south, east, or west. The only symbols that appear on the map are as follows:
The symbol # indicates a road cell that trucks can drive on. Roads are adjacent to at most two other road, intersection, or warehouse cells.
A single digit [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. The behavior of traffic lights is described below.
Exactly one character marks the warehouse where your truck starts.
Exactly one character marks the warehouse you want to deliver the cargo to.
The character represents grass. You cannot drive on these cells.
You have one cargo truck that starts at warehouse , and you should drive it to warehouse according to the rules below. For simplicity, time is divided into atomic units, or turns:
On a single turn, you may move the truck to an adjacent road, intersection, or warehouse cell, or remain in the same cell.
The truck may only enter an intersection cell if, on that turn, the traffic light for the intersection is green in the direction the truck is entering from. However, a truck already at the 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 never both at the same time. Intersections are described by their initial direction and two numbers indicating the traffic periods for east-west and north-south, respectively. For example, an intersection that is initially green for north-south and described by "2 3" will have a green light for north and south on turns –, for east and west on turns –, then again for north and south on turns –, and so on.
The input contains multiple test cases. Each test case starts with one line containing two integers and , separated by spaces. The map consists of rows (east-west) and columns (north-south) of grid cells (2 \leq m, n \leq 20). The next lines each contain characters, describing the map using the symbols defined above.
For each numbered intersection that appears on the map, in ascending order starting from , there is a line with the intersection number, followed by either a - or | character, and then two integers a_i and b_i (1 \leq a_i, b_i \leq 100), the east-west and north-south traffic periods, respectively. - indicates the light is initially green for east-west traffic; | indicates it is initially green for north-south traffic.
A blank line separates input test cases. A single line containing marks the end of input; do not process this case.
For each test case, output a single integer on one line: the minimum number of turns required to drive the truck from warehouse to warehouse . If it is impossible to reach warehouse , print a single word impossible.
(In the second example, it is actually quicker to take the bottom route than the top. However, your truck must wait west of intersection until it can enter on turn (when the light is green), then reach intersection on turn , wait again west of intersection until turn , and finally enter warehouse at the end of turn .)
Example 1