#include <bits/stdc++.h> using namespace std; typedef long long int LL; #define st first #define nd second #define PII pair <int, int> const int N = 2007; const LL INF = 1e18 + 9LL; const int DX[] = {-1, 0, 0, 1}; const int DY[] = {0, -1, 1, 0}; int n, m, k; char in[N][N]; int dist[N][N]; bool exist(int x, int y) { return 1 <= x && x <= n && 1 <= y && y <= m && in[x][y] == '.'; } int main() { scanf("%d %d %d", &n, &m, &k); for(int i = 1; i <= n; ++i) scanf("%s", in[i] + 1); for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) dist[i][j] = N * N; dist[1][1] = 0; priority_queue <pair <int, PII> > Q; Q.push({0, {1, 1}}); while(!Q.empty()) { auto [x, y] = Q.top().nd; Q.pop(); for(int t = 0; t < 4; ++t) { int nx = x + DX[t], ny = y + DY[t]; int eval = (nx + ny) < (x + y); if(exist(nx, ny) && dist[nx][ny] > dist[x][y] + eval) { dist[nx][ny] = dist[x][y] + eval; Q.push({-dist[nx][ny], {nx, ny}}); } } } assert(dist[n][m] != -1); int v = dist[n][m]; LL best = INF, cnt = 0; while(k--) { int a, b; scanf("%d %d", &a, &b); LL cand = 1LL * a * (n + m - 2) + 1LL * (a + b) * v; if(cand < best) best = cand, cnt = 0; if(cand == best) ++cnt; } printf("%lld %lld\n", best, cnt); return 0; }
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 | #include <bits/stdc++.h> using namespace std; typedef long long int LL; #define st first #define nd second #define PII pair <int, int> const int N = 2007; const LL INF = 1e18 + 9LL; const int DX[] = {-1, 0, 0, 1}; const int DY[] = {0, -1, 1, 0}; int n, m, k; char in[N][N]; int dist[N][N]; bool exist(int x, int y) { return 1 <= x && x <= n && 1 <= y && y <= m && in[x][y] == '.'; } int main() { scanf("%d %d %d", &n, &m, &k); for(int i = 1; i <= n; ++i) scanf("%s", in[i] + 1); for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) dist[i][j] = N * N; dist[1][1] = 0; priority_queue <pair <int, PII> > Q; Q.push({0, {1, 1}}); while(!Q.empty()) { auto [x, y] = Q.top().nd; Q.pop(); for(int t = 0; t < 4; ++t) { int nx = x + DX[t], ny = y + DY[t]; int eval = (nx + ny) < (x + y); if(exist(nx, ny) && dist[nx][ny] > dist[x][y] + eval) { dist[nx][ny] = dist[x][y] + eval; Q.push({-dist[nx][ny], {nx, ny}}); } } } assert(dist[n][m] != -1); int v = dist[n][m]; LL best = INF, cnt = 0; while(k--) { int a, b; scanf("%d %d", &a, &b); LL cand = 1LL * a * (n + m - 2) + 1LL * (a + b) * v; if(cand < best) best = cand, cnt = 0; if(cand == best) ++cnt; } printf("%lld %lld\n", best, cnt); return 0; } |