#include #include #include #include #include #include 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 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> djikstra(loc s, vector& matrix) { priority_queue, vector>, less>> q; vector> visited(N, vector(M)); vector> dist(N, vector(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 matrix; for (long long i = 0; i < N; i++) { cin >> s; matrix.push_back(s); } vector> 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> 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; }