TopCoder

aacpschool

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

66.7% (2/3)

Description

某座格局方正的城市可以被視為一個 $N\times M$ 的方格，並且建築都是佔據 $1\times 1$ 的單位方格，假設沒有建築的地方都是可以行走的道路，兩格空地視為相鄰如果他們有共同邊。

你現在要為一個機車充電站評估設點位置是否方便使用者，充電站一定會設置在空地上。你想要計算對於每塊空地，他到最近充電站的距離總和是多少？其中兩空地 $A, B$ 間距離表示至少要從 $A$ 移動幾次到相鄰空地才能到 $B$，充電站所在空地到最近充電站距離為 $0$。

保證對任意兩空地，都有路可以從其中一邊走到另外一邊。

Input Format

輸入第一行是三個空白分隔的整數 $N,M,K$，分別代表城市長寬以及充電站數。
接下來 $N$ 行每行 $M$ 個字元代表城市的地圖，第 $i$ 行第 $j$ 個字元代表座標 $(i,j)$ 的情況 $(1\le i\le N, 1\le j\le M)$，如果字元是 # 代表是建築，如果是 . 代表是空地。
接下來 $K$ 行每行兩個空白分隔的整數 $x,y$，代表座標 $(x,y)$ 有充電站。

輸入保證 $1\le N, M\le 1000$，$1\le K\le \min(10000, N\times M)$，$1\le x\le N$，$1\le y\le M$，並保證所有充電站都在空地上且位置兩兩相異。

Output Format

輸出一行一個整數表示總距離和。

Sample Input 1

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

Sample Output 1

Hints

Problem Source

CSAcademy

No.	Testdata Range	Constraints	Score
1	0	範例測資	0
2	0~16	無額外限制	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	524288	65536	1 2
1	1000	524288	65536	2
2	1000	524288	65536	2
3	1000	524288	65536	2
4	1000	524288	65536	2
5	1000	524288	65536	2
6	1000	524288	65536	2
7	1000	524288	65536	2
8	1000	524288	65536	2
9	1000	524288	65536	2
10	1000	524288	65536	2
11	1000	524288	65536	2
12	1000	524288	65536	2
13	1000	524288	65536	2
14	1000	524288	65536	2
15	1000	524288	65536	2
16	1000	524288	65536	2

761 . 充電站