#include <bits/stdc++.h> #define ll long long using namespace std; int n, m, t[2005][2005], dist[2005][2005], a, b, Q; queue<pair<int, int>> q[2]; string s; int32_t main() { ios_base::sync_with_stdio(0); cin >> n >> m >> Q; for(int i = 1; i <= n; i++) { cin >> s; for(int j = 1; j <= m; j++) { t[i][j] = (s[j - 1] == '.' ? 1 : 0); dist[i][j] = 1e9; } } int par = 0; dist[1][1] = 0; q[par].push({1, 1}); while(!q[par].empty()) { while(!q[par].empty()) { int x = q[par].front().first, y = q[par].front().second; q[par].pop(); if(dist[x][y] % 2 != par) continue; if(t[x + 1][y] && dist[x + 1][y] > dist[x][y]) { dist[x + 1][y] = dist[x][y]; q[par].push({x + 1, y}); } if(t[x][y + 1] && dist[x][y + 1] > dist[x][y]) { dist[x][y + 1] = dist[x][y]; q[par].push({x, y + 1}); } if(t[x - 1][y] && dist[x - 1][y] > dist[x][y] + 1) { dist[x - 1][y] = dist[x][y] + 1; q[!par].push({x - 1, y}); } if(t[x][y - 1] && dist[x][y - 1] > dist[x][y] + 1) { dist[x][y - 1] = dist[x][y] + 1; q[!par].push({x, y - 1}); } } par = !par; } ll ans = 1e18; int cnt = 0; while(Q--) { cin >> a >> b; ll len = 1LL * (n + m - 2) * a + 1LL * dist[n][m] * (a + b); if(len == ans) cnt++; else if(len < ans) { ans = len; cnt = 1; } } cout << ans << " " << cnt << "\n"; }
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 | #include <bits/stdc++.h> #define ll long long using namespace std; int n, m, t[2005][2005], dist[2005][2005], a, b, Q; queue<pair<int, int>> q[2]; string s; int32_t main() { ios_base::sync_with_stdio(0); cin >> n >> m >> Q; for(int i = 1; i <= n; i++) { cin >> s; for(int j = 1; j <= m; j++) { t[i][j] = (s[j - 1] == '.' ? 1 : 0); dist[i][j] = 1e9; } } int par = 0; dist[1][1] = 0; q[par].push({1, 1}); while(!q[par].empty()) { while(!q[par].empty()) { int x = q[par].front().first, y = q[par].front().second; q[par].pop(); if(dist[x][y] % 2 != par) continue; if(t[x + 1][y] && dist[x + 1][y] > dist[x][y]) { dist[x + 1][y] = dist[x][y]; q[par].push({x + 1, y}); } if(t[x][y + 1] && dist[x][y + 1] > dist[x][y]) { dist[x][y + 1] = dist[x][y]; q[par].push({x, y + 1}); } if(t[x - 1][y] && dist[x - 1][y] > dist[x][y] + 1) { dist[x - 1][y] = dist[x][y] + 1; q[!par].push({x - 1, y}); } if(t[x][y - 1] && dist[x][y - 1] > dist[x][y] + 1) { dist[x][y - 1] = dist[x][y] + 1; q[!par].push({x, y - 1}); } } par = !par; } ll ans = 1e18; int cnt = 0; while(Q--) { cin >> a >> b; ll len = 1LL * (n + m - 2) * a + 1LL * dist[n][m] * (a + b); if(len == ans) cnt++; else if(len < ans) { ans = len; cnt = 1; } } cout << ans << " " << cnt << "\n"; } |