#include <bits/stdc++.h> #define FOR(i, b, e) for (int i = (b); i <= (e); i++) #define FORD(i, b, e) for (int i = (e); i >= (b); i--) #define MP make_pair #define FS first #define ND second #define PB push_back #define ALL(x) x.begin(), x.end() using namespace std; using LL = long long; using PII = pair<int,int>; using PLL = pair<LL,LL>; using VI = vector<int>; using VLL = vector<LL>; template<class T> using V = vector<T>; template<class T> int sz(const T& a) { return (int)a.size(); } template<class T> void amin(T& a, T b) { a = min(a, b); } template<class T> void amax(T& a, T b) { a = max(a, b); } const int inf = 1e9; const LL infl = 1e18; const PII dirs[] = { MP(-1, 0), MP(1, 0), MP(0, -1), MP(0, 1) }; int n, m, k; char s[2001][2002]; int dist[2001][2001]; queue<PII> q; LL best = infl; int cnt = 0; int main() { scanf("%d %d %d", &n, &m, &k); FOR(i, 1, n) scanf("%s", &s[i][1]); q.push(MP(1, 1)); s[1][1] = 'V'; while (sz(q)) { auto [x, y] = q.front(); q.pop(); for (auto [dx, dy] : dirs) { int x1 = x + dx; int y1 = y + dy; if (1 <= x1 && x1 <= n && 1 <= y1 && y1 <= m && s[x1][y1] == '.') { dist[x1][y1] = dist[x][y] + 1; s[x1][y1] = 'V'; q.push(MP(x1, y1)); } } } int x = n + m - 2 + (dist[n][m] - (n + m - 2)) / 2; int y = (dist[n][m] - (n + m - 2)) / 2; FOR(i, 1, k) { LL a, b; scanf("%lld %lld", &a, &b); LL score = a * x + b * y; if (score < best) { best = score; cnt = 1; } else if (score == best) cnt++; } printf("%lld %d\n", best, cnt); }
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 73 74 75 76 77 78 | #include <bits/stdc++.h> #define FOR(i, b, e) for (int i = (b); i <= (e); i++) #define FORD(i, b, e) for (int i = (e); i >= (b); i--) #define MP make_pair #define FS first #define ND second #define PB push_back #define ALL(x) x.begin(), x.end() using namespace std; using LL = long long; using PII = pair<int,int>; using PLL = pair<LL,LL>; using VI = vector<int>; using VLL = vector<LL>; template<class T> using V = vector<T>; template<class T> int sz(const T& a) { return (int)a.size(); } template<class T> void amin(T& a, T b) { a = min(a, b); } template<class T> void amax(T& a, T b) { a = max(a, b); } const int inf = 1e9; const LL infl = 1e18; const PII dirs[] = { MP(-1, 0), MP(1, 0), MP(0, -1), MP(0, 1) }; int n, m, k; char s[2001][2002]; int dist[2001][2001]; queue<PII> q; LL best = infl; int cnt = 0; int main() { scanf("%d %d %d", &n, &m, &k); FOR(i, 1, n) scanf("%s", &s[i][1]); q.push(MP(1, 1)); s[1][1] = 'V'; while (sz(q)) { auto [x, y] = q.front(); q.pop(); for (auto [dx, dy] : dirs) { int x1 = x + dx; int y1 = y + dy; if (1 <= x1 && x1 <= n && 1 <= y1 && y1 <= m && s[x1][y1] == '.') { dist[x1][y1] = dist[x][y] + 1; s[x1][y1] = 'V'; q.push(MP(x1, y1)); } } } int x = n + m - 2 + (dist[n][m] - (n + m - 2)) / 2; int y = (dist[n][m] - (n + m - 2)) / 2; FOR(i, 1, k) { LL a, b; scanf("%lld %lld", &a, &b); LL score = a * x + b * y; if (score < best) { best = score; cnt = 1; } else if (score == best) cnt++; } printf("%lld %d\n", best, cnt); } |