761 . 充電站
TopCoder
Tags
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
#..
.#.
...
1 2
3 1
Sample Output 1
7
Hints
Problem Source
CSAcademy
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~16 | 無額外限制 | 100 |