1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
/*
* .....# 6 + 7 + 8 + 9 + 10 = 21 + 19 = 40
* .###.# 5
* ...#.# 4 + 5 + 6 = 15
* .##### 3
* ..^..# 2 + 1 + 0 + 1 + 2 = 6
* ######
*
*
3 3 1
.##
...
##.
1 1
10 10 10
+.####...#
####.#.##.
...#....##
.###......
###.....#.
..#.......
##.......#
..#.##.###
...###.##.
.#...#...#
1 1
1 7
2 10
3 1
6 1
8 1
9 10
10 8
5 2
1 3
*/
typedef pair<long long, long long> loc;
long long N, M, K;
loc dir[] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
loc operator+(const loc& p1, const loc& p2) {
return { p1.first + p2.first, p1.second + p2.second };
}
vector<vector<long long>> djikstra(loc s, vector<string>& matrix) {
priority_queue<pair<long long, loc>, vector<pair<long long, loc>>, less<pair<long long, loc>>> q;
vector<vector<bool>> visited(N, vector<bool>(M));
vector<vector<long long>> dist(N, vector<long long>(M, -1));
dist[s.first][s.second] = 0;
q.push({ 0, s });
while (!q.empty()) {
loc c = q.top().second;
q.pop();
visited[c.first][c.second] = true;
for (int i = 0; i < 4; i++) {
loc ne = c + dir[i];
if (0 > ne.first || ne.first >= N || 0 > ne.second || ne.second >= M || visited[ne.first][ne.second] || matrix[ne.first][ne.second] == '#') continue;
if (dist[ne.first][ne.second] == -1 || dist[c.first][c.second] + 1 < dist[ne.first][ne.second]) {
dist[ne.first][ne.second] = dist[c.first][c.second] + 1;
q.push({ dist[ne.first][ne.second], ne});
}
}
}
return dist;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M >> K;
string s;
vector<string> matrix;
for (long long i = 0; i < N; i++) {
cin >> s;
matrix.push_back(s);
}
vector<pair<long, long>> food;
for (long long i = 0; i < K; i++) {
long long ri, ci;
cin >> ri >> ci;
food.push_back({ri-1, ci-1});
}
long long sum = 0;
for (long long i = 0; i < N; i++) {
for (long long j = 0; j < M; j++) {
if (matrix[i][j] == '#') continue;
vector<vector<long long>> dist = djikstra({i,j}, matrix);
// cout << endl << i << " " << j << " is at" << endl;
// for (long long i = 0; i < N; i++) {
// for (long long j = 0; j < M; j++) {
// cout << i << " " << j << " dist " << dist[i][j] << endl;
// }
// }
long long mind = -1;
for (auto f : food) {
if (matrix[f.first][f.second] == '#') continue;
if (mind == -1) {
mind = dist[f.first][f.second];
continue;
}
mind = min(mind, dist[f.first][f.second]);
}
// cout << "mind " << mind << endl;
sum += mind;
}
}
cout << sum << endl;
}
|
