#include <iostream> #include <cstdio> using namespace std; typedef long long ll; const int M = 2010; char T[M][M]; int Q[M*M]; int D[M*M]; int dx[] = {0,-1,0,1}; int dy[] = {-1,0,1,0}; int main() { int n,m,k; scanf("%d%d%d", &n,&m,&k); for (int i=0;i<n;i++) { scanf("%s", T[i]); } Q[0]=0; D[0]=1; int a = 0, b = 1; int d; while (a < b) { int v=Q[a++]; int ay = v/M; int ax = v%M; if (ay == (n-1) && ax == (m-1)) { d = D[v]; break; } for (int i=0;i<4;i++) { int nx = ax + dx[i]; int ny = ay + dy[i]; if (nx >=0 && nx < m && ny >= 0 && ny < n && T[ny][nx] == '.') { int ee = ny * M + nx; if (!D[ee]) { Q[b++]=ee; D[ee] = D[v]+1; } } } } d--; ll h = (d - (n + m - 2)) / 2; ll ma = (n + m - 2) + h; ll bsf = 100000000000000000L; int cbsf = 0; int c1, c2; for (int i=0; i<k;i++) { scanf("%d%d", &c1, &c2); ll cv = ma * c1 + h * c2; if (cv < bsf) { bsf = cv; cbsf = 1; } else if (cv == bsf) { cbsf++; } } printf("%lld %d\n", bsf, cbsf); 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 71 72 | #include <iostream> #include <cstdio> using namespace std; typedef long long ll; const int M = 2010; char T[M][M]; int Q[M*M]; int D[M*M]; int dx[] = {0,-1,0,1}; int dy[] = {-1,0,1,0}; int main() { int n,m,k; scanf("%d%d%d", &n,&m,&k); for (int i=0;i<n;i++) { scanf("%s", T[i]); } Q[0]=0; D[0]=1; int a = 0, b = 1; int d; while (a < b) { int v=Q[a++]; int ay = v/M; int ax = v%M; if (ay == (n-1) && ax == (m-1)) { d = D[v]; break; } for (int i=0;i<4;i++) { int nx = ax + dx[i]; int ny = ay + dy[i]; if (nx >=0 && nx < m && ny >= 0 && ny < n && T[ny][nx] == '.') { int ee = ny * M + nx; if (!D[ee]) { Q[b++]=ee; D[ee] = D[v]+1; } } } } d--; ll h = (d - (n + m - 2)) / 2; ll ma = (n + m - 2) + h; ll bsf = 100000000000000000L; int cbsf = 0; int c1, c2; for (int i=0; i<k;i++) { scanf("%d%d", &c1, &c2); ll cv = ma * c1 + h * c2; if (cv < bsf) { bsf = cv; cbsf = 1; } else if (cv == bsf) { cbsf++; } } printf("%lld %d\n", bsf, cbsf); return 0; } |