124 . Oh, Those Achin' Feet

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description


In recent days, a number of people have
been injured after being pushed off the sidewalks due to overcrowding.
City Hall is interested in figuring out how much pedestrian traffic its
sidewalks receive every day. The results of this study will be used to
determine whether the city needs to fund more sidewalks. The city has
surveyed various buildings in several blocks to determine the traffic
patterns they generate. Your job is to take this survey data and convert
it into sidewalk utilization information.


Your program will read in the
size of the map and a map of several city blocks. Buildings, streets, and
building entrance/exits will be marked on the map. You will also be given
a list of pedestrian load between several pairs of exits and entrances.
Your program will determine the paths used by pedestrians between each
source and destination, add up the total pedestrian load from all paths
using each street, and output a table of the total pedestrian load on each
square.

Notes

  • The map is divided into squares. Each square of the map can be a street square, a building square, or an entrance/exit square. An entrance/exit square serves as both entrance and exit for that building. There will be no more than 90 street squares in the map.

  • People will always follow the shortest path between their origin and destination. No shortest path will exceed 75 squares.

  • If there are multiple equal-length shortest paths, the load will be divided equally amongst the paths. For shortest paths, there will be fewer than 50000 equal-length path combinations.

  • If a building entrance/exit has multiple sides facing a street (for example, a corner of a building), the pedestrians may enter or exit through any street-facing side.

  • All movement will be strictly N, E, S, or W. No diagonal movement is permitted.

  • Pedestrians cannot move through buildings or off the edge of the map.

  • For convenience, you may ignore the fact that each street section may have two sidewalks.

  • Traffic load is not applied to the actual exit/entrance squares themselves.

  • If an origin and destination are adjacent on the map, pedestrians may move directly between them. In this case, there is no resulting load placed on any portion of the map because no streets are used.

Input Format

Line 1: X Y

X is the number of columns in the map, Y is the
number of rows. Each is a positive integer less than 20.


Lines 2-(Y+1):


Each line contains exactly X symbols indicating the contents of that square
on the map. The symbols are:


    X: building, non-entrance/exit


    .: (period) street


    {A-O}: letter indicating exit/entrance. Each letter may occur at
most once.


Lines (Y+2)-?:


Each line indicates a pedestrian route and
specifies a source, destination, and pedestrian load. Source and
destination will each be a letter {A-O} with no spaces in
between. The
load factor will be a nonnegative integer, separated from the destination
by whitespace. Source and destination will never be equal. At most 25
routes will be given. There will be a valid path in the map for each
requested route.


The test case will terminate with the line:


XX 0


After this line, a next test case can follow.
The input file is terminated by two zeros in place of a map size.

Output Format


The output consists of Y lines, each with X space-separated fields
indicating the load factor. Each load factor is printed to two decimal
places with 3 spaces for integer digits (C 6.2 format).

Sample Input 1

4 4
....
A.X.
XXX.
B...
AB 2
BA 1
XX 0
0 0

Sample Output 1

  1.50   3.00   3.00   3.00
  0.00   1.50   0.00   3.00
  0.00   0.00   0.00   3.00
  0.00   3.00   3.00   3.00

Hints

Problem Source

Migrated from old NTUJ.

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 20
Submit
Back to Top