#include <cstdio> #include <cstdlib> #include <algorithm> #include <queue> using namespace std; const int N_MAX = 2000; const int M_MAX = 2000; int T[N_MAX][M_MAX]; int W[N_MAX][M_MAX]; int n, m, k; void try_add(queue< pair<int, int> > &Q, int x, int y, int k, int diff) { if (x < 0 || x >= n) return; if (y < 0 || y >= m) return; if (T[x][y] == 0) return; if (W[x][y] >= 0) return; W[x][y] = k + diff; Q.push(make_pair(x, y)); } int main() { scanf("%d %d %d", &n, &m, &k); getchar(); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { char c = getchar(); if (c == '.') { T[i][j] = 1; } else { T[i][j] = 0; } W[i][j] = -1; } getchar(); } W[n-1][m-1] = 0; queue< pair<int, int> > Q; Q.push(make_pair(n-1, m-1)); while (!Q.empty()) { pair<int, int> elem = Q.front(); Q.pop(); try_add(Q, elem.first-1, elem.second, W[elem.first][elem.second], 0); try_add(Q, elem.first, elem.second-1, W[elem.first][elem.second], 0); try_add(Q, elem.first+1, elem.second, W[elem.first][elem.second], 1); try_add(Q, elem.first, elem.second+1, W[elem.first][elem.second], 1); } long long int r = -1; int c = 0; for (int i = 0; i < k; ++i) { long long int a, b; scanf("%lld %lld", &a, &b); long long int cur = (n + m - 2) * a + W[0][0] * (a + b); if (r == -1 || cur < r) { r = cur; c = 1; } else if (cur == r) { ++c; } } printf("%lld %d\n", r, c); 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 | #include <cstdio> #include <cstdlib> #include <algorithm> #include <queue> using namespace std; const int N_MAX = 2000; const int M_MAX = 2000; int T[N_MAX][M_MAX]; int W[N_MAX][M_MAX]; int n, m, k; void try_add(queue< pair<int, int> > &Q, int x, int y, int k, int diff) { if (x < 0 || x >= n) return; if (y < 0 || y >= m) return; if (T[x][y] == 0) return; if (W[x][y] >= 0) return; W[x][y] = k + diff; Q.push(make_pair(x, y)); } int main() { scanf("%d %d %d", &n, &m, &k); getchar(); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { char c = getchar(); if (c == '.') { T[i][j] = 1; } else { T[i][j] = 0; } W[i][j] = -1; } getchar(); } W[n-1][m-1] = 0; queue< pair<int, int> > Q; Q.push(make_pair(n-1, m-1)); while (!Q.empty()) { pair<int, int> elem = Q.front(); Q.pop(); try_add(Q, elem.first-1, elem.second, W[elem.first][elem.second], 0); try_add(Q, elem.first, elem.second-1, W[elem.first][elem.second], 0); try_add(Q, elem.first+1, elem.second, W[elem.first][elem.second], 1); try_add(Q, elem.first, elem.second+1, W[elem.first][elem.second], 1); } long long int r = -1; int c = 0; for (int i = 0; i < k; ++i) { long long int a, b; scanf("%lld %lld", &a, &b); long long int cur = (n + m - 2) * a + W[0][0] * (a + b); if (r == -1 || cur < r) { r = cur; c = 1; } else if (cur == r) { ++c; } } printf("%lld %d\n", r, c); return 0; } |