shunfurh 于 2017.09.19 16:55 提问

Afshung Pizza Delivery

Description

Afshung-Pizza chain, a door-to-door pizza delivery service for Hamedung, a Sildavya district, needs your help for fastest possible pizza delivery plan. With a GIS device that shows all streets of the Hamedung, each delivery boy can find a fast route to deliver the pizza to the place of order. The Elyasung Company that sells and supports this GIS device needs your help to reprogram the device to provide even a faster route plan.

Hamedung is a rectangular shape district with many two-way streets that are all rectilinear. To show the map, the GIS device uses text characters as shown in the sample test data. In this format, each one kilometer of a street is shown by a dash (-) or a pipe (|) showing that the street is either in west-east or in north-south direction. A plus (+) on the map indicates a sharp 90 degree turn (with length zero) on that position without any traffic light. All such turns are marked with +. An intersection is shown by an integer τ on that position. τ is the timing of the traffic light at that intersection which can be either three or four way. To have a smooth and accident-free district, the municipality of Hamedung has forced that every traffic light has only one green light and two or three red lights for three or four intersections respectively. One of the lights in that intersection remains green for τ minutes (i.e., during [x, x + τ) time for some x) and others are red. In the next τ minutes, one other direction turns green as if the green light turns counter clockwise. This rule is observed in all intersections.

The time is set to zero at the beginning when the delivery boy starts moving. At this time, all traffic signals are set such that only the southern light (or the northern light if no southern light exists) of each intersection is set to green, and other lights at this intersection are set to red.

Note that the only positions that the driver can change his direction are: a turn (+), or an intersection (represented by a digit). As an example, if we have a pattern like -|- in the map, the driver cannot cross the pipe if he is moving from left to right or right to left, neither can he turn left or right, since there is no intersection at this location.

Given the complete map described above, the location of an Afshung-Pizza branch, marked by S, and the location of the final delivery place, marked by D, you are to write a program for GIS device to automatically find the fastest possible route to deliver pizza from S to D. Note the following assumptions:

S and D are parts of a street (replacing either a - or |)
S and D are not adjacent to any intersection or turn.
S and D are not adjacent to each other.
Intersections and/or turns are at least one kilometer apart.
'S', 'D', '+', and each digit have zero kilometer length.
Speed of delivery boy is one kilometer per minute.
Traffic that faces a green light can move in all directions. No straight move or turns are allowed at red light.
There is no traffic jam or other obstacles on the way.
Asterisk characters (*) show the border of the district.
Input

The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains two integer numbers: N (1<= N <= 100) the number of rows of the map, and M (2 <= M <= 100) the number of columns of the map. Followed by the first line, there will be N lines, each containing a string of length M, consisting of '-', '|', '+', ' ', '*', 'S', 'D' or digits from '1' to '9'. Also, assume that the total number of intersections and turns (+) is at most 100.
Output

There should be one line in the output per test case containing a single number, the minimum time to drive from S to D, if there exists, otherwise the word impossible (with lower-case letters).
Sample Input

1
10 10

-D-3---+

• | |*
• | +-+*
• |-| * *---4-1- *
• | | *
• | | * S--2-+ * ********* Sample Output

15

1个回答

caozhy      2017.10.04 23:54

Hoj 1020 Afshung Pizza Delivery

CodeChef November Challenge 2013 题解

1628 Pizza Delivery
1628 Pizza Delivery There is a pizza house located on a straight road, and there are many houses along the road which are customers to the pizza house. To attract more orders from his customers, the
Pizza V1.73 完美版+CX助手+pdg转PDF软件包

Codeforces895A. Pizza Separation
A. Pizza Separation time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Students Vasya and Petya are studying at
PIZZA1.7.3破解版（解密所有超星的PDG文件格式）.rar
PIZZA1.7.3破解版（解密所有超星的PDG文件格式） Pizza 解密超星66H、68H格式的pdg文件
Uva-1628 Pizza Delivery(机智DP)

GETZ PIZZA – Home Delivery Management
GETZ PIZZA is a known pizza parlor批萨店 in the city. Looking at the increasing demand at workplaces and locality, we plan to extend the services to, Deliver@Home–free delivery within the city limits bas