DMOPC '14 Contest 1 P5 - Surprise Teleport

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M
Author:
Sentient
Problem type

However, you quickly realize that Mr. Sidhu can't walk through walls! Therefore, you must now somehow include these obstacles into your program. The input will include a grid that will consist of O (representing an empty space) and X (representing an obstacle or otherwise unavailable space). You should note that each grid space is equal to one metre in length. It is guaranteed that the starting and destination points will be available (O, that is) and that the Main Office can be reached by walking.

What he does not know, however, is that the school's former physics teacher installed invisible teleportation devices over the summer to provide a more efficient means for teachers to move around. She also configured it such that it would only work for Mr. Sidhu and no one else.

Unfortunately, she forgot about the devices — and she retired. As Mr. Sidhu walks down the hall, he is instantly teleported to the Main Office, his destination. Since he doesn't particularly enjoy being randomly teleported, he contacted the teacher and convinced her to remove the devices.

Being the curious student you are, you happened to stumble over a copy of the map of the teleportation devices on the teacher's desk of the classroom you have physics in, which contains the exact location of the devices as well as mentions that it would only affect Mr. Sidhu.

Since you are also a very compassionate student, you decide to show him the map but are disappointed when he tells you that the devices no longer exist. Therefore, to make him regret his decision, you decide to write a program that calculates exactly how much time Mr. Sidhu could have saved had he known the exact locations of the devices.

Input Specification

The first line of input will consist of the number of rows and columns R, C (1 \le R, C \le 1000), separated by one space. The next line represents his starting point and the following line is the Main Office. Note that rows and columns in this problem are zero-indexed. This is followed by R lines containing the grid as described above.

The next line of input will be T (0 \le T \le R \times C), the number of teleportation devices. This will be followed by T lines, consisting of two positive integers each separated by one space representing the coordinates of that device, the former being the row number and the latter the column number. You can assume that teleportation devices will not be on walls.

Output Specification

Your output should be the time he could have gained, in seconds.

Sample Input

5 5
4 4
1 2
OOXOO
OXOXO
OOOXX
XOXOX
OOOOO
1
3 3

Sample Output

5

Explanation for Sample Output

There is one device at 3, 3. He starts at 4, 4, the bottom-right of the grid. The length of the shortest path ignoring (walking over the tile) the device is 7 metres. Walking at 1 m/s means it will take him 7 seconds. But a teleportation device is only 2 metres away, thus allowing him to complete his journey in 2 seconds. The output should be 5, as he would have saved 5 seconds.

Comments


  • 0
    fraud  commented on July 19, 2024, 7:01 p.m. ← edit 2

    Just in case anybody is confused (I was lol):

    the coordinates are flipped (they are given as (y, x)) -> if you test it in the sample case as (x, y), you would get answer 3 instead of 5.

    also, you should output the max amount of time that can be saved, not the amount of time per teleporter.


  • 1
    kevze  commented on June 17, 2020, 3:11 p.m. ← edit 2

    It should be noted that one of the cases includes a path where Mr. Sidhu's only path to the main office crosses a teleporter.

    Edit: for example

    5 5
4 4
1 2
OOXOO
OXOXO
OOOXX
XOXOX
OOOOO
1
3 1

    And correct output is 3.


  • 5
    RyanLi  commented on Jan. 10, 2020, 5:54 p.m.

    Note: He can start directly on a teleporter


  • 13
    Firebrand  commented on July 26, 2019, 9:32 p.m.

    Could be worth mentioning that the coordinates are from index 0 and not 1 - that tripped me up a little bit.


  • 2
    AlanCCCL2S18  commented on March 30, 2018, 7:36 p.m.

    Can he walk diagonally or not?


    • 5
      wleung_bvg  commented on March 31, 2018, 12:24 a.m.

      No, he cannot walk diagonally. Only up, down, left, and right (if there is no wall).


  • 23
    hezeyu2007  commented on March 25, 2018, 5:36 p.m. ← edited

    So is saving 5 seconds of his life so important for Mr. Sidhu? :)


  • 8
    max  commented on Dec. 14, 2017, 12:35 a.m.

    Clarification

    Will the amount of time Mr. Sidhu could have saved always be a positive integer?

    ie. If there was only one portal farther away from the starting point than the main office, would we output a negative integer?

    thanks


    • 13
      aeternalis1  commented on Dec. 14, 2017, 1:46 a.m.

      If the portal is further away than the main office, he would simply go straight into the office and never take the portal, saving 0 time. Thus you would output 0.