oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

bottle Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

bottle.html

JOI-kun lives in IOI city. He knows that it gets very hot throughout the year in IOI city.

IOI city is a rectangular city of rectangular cells with with height H cells and width W cells. Of these cells, some are buildings, fields or walls. There are P buildings, numbered from 1 to P.

JOI-kun can travel to the buildings and fields of IOI city. JOI-kun can travel from any cell to its adjacent cells (in other words, the cells that share an edge with the current cell). However, JOI-kun may not leave IOI city.

JOI-kun must walk from building to building to complete a variety of errands. Although buildings have air-conditioning, fields do not. Since the sun is very strong, the fields are very hot and JOI-kun needs 1 unit of water to travel 1 cell in a field. Since there are no vending machines in fields, it is normal to carry a water bottle in IOI city. A water bottle of size x can contain at most x units of water. Since all buildings have a water supply, it is possible to refil water bottles at all buildings.

It is inconvenient to have to carry a big water bottle. JOI-kun wants to mimimize the size of the water bottle he has to carry while moving between buildings. Help JOI-kun determine the minimum size of the water bottle he has to carry in order to move between any pair of buildings.

You will be given a map of IOI city and Q queries. The jth query (1 ≤ j ≤ Q) asks for the minimum size of the water bottle JOI-kun has to carry in order to move from building Si to building Ti. Write a program to answer these queries.

Input

Read from standard input.

  • The first line contains four integers H, W, P and Q. This means IOI city has height H and width W and contains P buildings. There will be Q queries.
  • The next H lines contain the map of IOI city. On the rth line (1 ≤ r ≤- H), there are W characters. The cth character (1 ≤ c ≤ W) on each line represents the cell in IOI city that is at the rth row from the top and the cth column from the left. A '.' means that the cell is either a building or a field, and a '#' means that the cell is a wall.
  • On the jth line of the next P lines (1 ≤ j ≤ P), there are 2 integers, Aj and Bj. This means that building j is at the cell on the Ajth row from the top and the Bjth column from the left. It is guaranteed that the cell is a '.' on the map given above.
  • On the ith line of the next Q lines (1 ≤ i ≤ Q), there are 2 integers, Si and Ti. This means that the ith query asks for the minimum size of the water bottle JOI-kun has to carry in order to move from building Si to building Ti.

Output

Print Q lines to standard output.

On the ith line (1 ≤ i ≤ Q), print the minimum size of the water bottle JOI-kun has to carry to move from building Si to building Ti. If it is impossible to move from building Si to building Ti, print -1.

Constraints

All test cases meet the following constraints.

  • 1 ≤ H ≤ 2 000.
  • 1 ≤ W ≤ 2 000.
  • 2 ≤ P ≤ 200 000.
  • 1 ≤ Q ≤ 200 000.
  • 1 ≤ Aj ≤ H (1 ≤ j ≤ P).
  • 1 ≤ Bj ≤ W (1 ≤ j ≤ P).
  • (Ai, Bi) ≠ (Aj, Bj) (1 ≤ i < j ≤ P).
  • 1 ≤ Si < Ti ≤ P (1 ≤ i ≤ Q).

Subtasks

Subtask 1 (10 points):

The following constraints are met.

  • H ≤ 200.
  • W ≤ 200.
  • P ≤ 200.

Subtask 2 (30 points):

The following constraints are met.

  • P ≤ 5 000.
  • Q = 1.

Subtask 3 (30 points):

The following constraints are met.

  • P ≤ 5 000.
  • Q ≤ 10 000.

Subtask 4 (30 points):

No further constraints.

Sample Input 1

5 5 4 4
.....
..##.
.#...
..#..
.....
1 1
4 2
3 3
2 5
1 2
2 4
1 3
3 4

Sample Output 1

3
4
4
2

Explanation

According to the input, the layout of IOI city is shown in the following grid. Black squares represent a wall and numbers represent the number of the building on the cell. Empty cells represent fields.

1
◼ ◼ 4
◼ 3
2 ◼

For example, consider the path between buildings 2 and 4.

1
◼ ◼ 4
◼ 3 ·
2 ◼ ·
· · · ·

If you do not want to pass by other buildings, the minimum number of fields and thus the minimum size of the bottle needed to travel from building 2 to building 4 is 6.

1 · · · ·
· ◼ ◼ 4
· ◼ 3
· 2 ◼

However, we can instead move from building 2 to 1, passing by 3 fields, and then move from building 1 to 4, passing by 4 fields. Thus, since we can refil the water bottle at building 1, the minimum size of the water bottle JOI-kun needs is 4. No other path requires a smaller water bottle.

Sample Input 2

5 5 3 2
...#.
..#..
#....
.##..
...#.
1 3
5 2
1 5
1 2
1 3

Sample Output 2

-1
7

Explanation

In this test case, there is no way to move from building 1 to building 2.

Tags

JOI 2013/2014, Graph Theory, Breadth First Search, Union Find Disjoint Set

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
11092s512MBMinimum
230152s512MBMinimum
330112s512MBMinimum
430122s512MBMinimum
5022s512MBMinimum

Judge Compile Command

g++-8 ans.cpp -o bottle -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.