Problem : 364 - 2A. 水壺

Problem Statistics

Solved Member: 7　　Submission: 65　　User Tried: 10

Statement:

最近天蓬國的沙漠化越來越嚴重了。天蓬國的地圖可以切成長 H 寬 W 個格子，每個格子有可能為「建築物」、「沙漠」或者是「牆壁」。市內有 P 動建築物，建築物由 1 標號到 P。

天蓬國的移動方式很特別，地圖中牆壁不可以行走，而建築物和沙漠則是可以行走的格子。每次可以移動到有相鄰邊的格子上。

由於沙漠缺水很熱，每經過一次沙漠就會消耗一單位的水，因此天蓬國的人都習慣帶著水壺移動以備不需。並且每一棟都提供飲水機可以讓你把水壺的水補滿。

為了在市內的兩棟建築物之間移動你決定買一個水壺，大小 x 的水壺恰好能裝 x 單位的水。但是你非常困擾到底該買多大的水壺才好，因此你決定寫一個程式來計算。

Input:Output:

第一行依序有四個整數 H,W,P,Q，代表市的大小為 H*W，並且有 P 棟建築物以及 Q 筆詢問。
接下來 H 行，每行有長度 W 的字串。字串為「#」和「.」字元所構成，「#」代表牆壁，「.」代表該格為建築物或者沙漠。
接下來 P 行，每一行有兩個數字 Ai,Bi，代表市中由上往下的第 Ai 列由左往右的第 Bi 行有一棟建築物 i。
接下來 Q 行，每行有兩個整數 Si, Ti，代表你希望從第 Si 棟建築移動到第 Ti 棟建築。

限制：
1 ≤ H,W ≤ 2000
1 ≤ P,Q ≤ 200000
1 ≤ Ai ≤ H
1 ≤ Bi ≤ W
1 ≤ Si < Ti ≤ P
P棟建築位置不會重複

Subtask 1：(10分)
H,W,P ≤ 200

Subtask 2：(30分)
P ≤ 5000
Q = 1

Subtask 3：(30分)
P ≤ 5000
Q ≤ 10000

輸出 Q 行，每一行請輸出該筆詢問中，至少要買多大的水壺才能在兩棟建築之間行走。若沒有辦法在兩棟建築之間移動請輸出 -1。

Sample Input:Sample Output:

SAMPLE A:
5 5 4 4
.....
..##.
.#...
..#..
.....
1 1
4 2
3 3
2 5
1 2
2 4
1 3
3 4

SAMPLE B:
5 5 3 2
...#.
..#..
#....
.##..
...#.
1 3
5 2
1 5
1 2
1 3

SAMPLE A:
3
4
4
2

SAMPLE B:
-1
7

HINT:

下圖為 SAMPLE A 的地圖，塗黑代表不能移動，標數字代表建築物的編號：

我們考慮 2 到 4 的路徑：

如果從 2 到 4 不經過其他的建築物的話，至少像上圖左邊一樣，會經過 6 格沙漠，水壺大小至少要 6。

但如果像右圖中由 2 先走到 1，再走到 4，只需要大小為 4 的水壺就可以移動了。

Source:

2013/2014 JOI 合宿 2模（日本IOI國手考）

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	1000ms	262144kb
0-2	1000ms	262144kb
1-1	1000ms	262144kb	10
1-2	1000ms	262144kb
1-3	1000ms	262144kb
1-4	1000ms	262144kb
1-5	1000ms	262144kb
1-6	1000ms	262144kb
1-7	1000ms	262144kb
1-8	1000ms	262144kb
1-9	1000ms	262144kb
2-1	3000ms	262144kb	30
2-2	3000ms	262144kb
2-3	3000ms	262144kb
2-4	3000ms	262144kb
2-5	3000ms	262144kb
2-6	3000ms	262144kb
2-7	3000ms	262144kb
2-8	3000ms	262144kb
2-9	3000ms	262144kb
2-10	3000ms	262144kb
2-11	3000ms	262144kb
2-12	3000ms	262144kb
2-13	3000ms	262144kb
2-14	3000ms	262144kb
2-15	3000ms	262144kb
3-1	3000ms	262144kb	30
3-2	3000ms	262144kb
3-3	3000ms	262144kb
3-4	3000ms	262144kb
3-5	3000ms	262144kb
3-6	3000ms	262144kb
3-7	3000ms	262144kb
3-8	3000ms	262144kb
3-9	3000ms	262144kb
3-10	3000ms	262144kb
3-11	3000ms	262144kb
4-1	3000ms	262144kb	30
4-2	3000ms	262144kb
4-3	3000ms	262144kb
4-4	3000ms	262144kb
4-5	3000ms	262144kb
4-6	3000ms	262144kb
4-7	3000ms	262144kb
4-8	3000ms	262144kb
4-9	3000ms	262144kb
4-10	3000ms	262144kb
4-11	3000ms	262144kb
4-12	3000ms	262144kb