#include <bits/stdc++.h> using namespace std; #define ALL(x) (x).begin(), (x).end() template<class C> void mini(C &a5, C b5) { a5 = min(a5, b5); } template<class C> void maxi(C &a5, C b5) { a5 = max(a5, b5); } #ifdef LOCAL const bool debug = true; #else const bool debug = false; #define cerr if (true) {} else cout #endif #define int long long #define double long double const int INF = 1e18; const int mod = 1e9 + 7; int dp[2010][2010]; bool czy[2010][2010]; int dist[2010][2010]; vector<pair<int, int> > kier = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m, k; cin >> n >> m >> k; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { char c; cin >> c; if (c == '.') czy[i][j] = true; dist[i][j] = -1; } } dist[1][1] = 0; queue<pair<int, int> > kol; kol.push({1, 1}); while (!kol.empty()) { int x = kol.front().first; int y = kol.front().second; kol.pop(); int d = dist[x][y]; for (auto [dx, dy] : kier) { x += dx; y += dy; if (dist[x][y] == -1 && czy[x][y]) { dist[x][y] = d + 1; kol.push({x, y}); } x -= dx; y -= dy; } } int aa = n + m - 2; int d = dist[n][m]; d -= aa; aa += d / 2; int bb = d / 2; pair<int, int> res = {INF, 0}; while (k--) { int a, b; cin >> a >> b; int ile = a * aa + b * bb; if (ile < res.first) res = {ile, 0}; if (ile == res.first) res.second++; } cout << res.first << " " << res.second; return 0; }/* 2 5 4.X......X. 2 1 2 2 1 7 2 1 */
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 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 | #include <bits/stdc++.h> using namespace std; #define ALL(x) (x).begin(), (x).end() template<class C> void mini(C &a5, C b5) { a5 = min(a5, b5); } template<class C> void maxi(C &a5, C b5) { a5 = max(a5, b5); } #ifdef LOCAL const bool debug = true; #else const bool debug = false; #define cerr if (true) {} else cout #endif #define int long long #define double long double const int INF = 1e18; const int mod = 1e9 + 7; int dp[2010][2010]; bool czy[2010][2010]; int dist[2010][2010]; vector<pair<int, int> > kier = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m, k; cin >> n >> m >> k; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { char c; cin >> c; if (c == '.') czy[i][j] = true; dist[i][j] = -1; } } dist[1][1] = 0; queue<pair<int, int> > kol; kol.push({1, 1}); while (!kol.empty()) { int x = kol.front().first; int y = kol.front().second; kol.pop(); int d = dist[x][y]; for (auto [dx, dy] : kier) { x += dx; y += dy; if (dist[x][y] == -1 && czy[x][y]) { dist[x][y] = d + 1; kol.push({x, y}); } x -= dx; y -= dy; } } int aa = n + m - 2; int d = dist[n][m]; d -= aa; aa += d / 2; int bb = d / 2; pair<int, int> res = {INF, 0}; while (k--) { int a, b; cin >> a >> b; int ile = a * aa + b * bb; if (ile < res.first) res = {ile, 0}; if (ile == res.first) res.second++; } cout << res.first << " " << res.second; return 0; }/* 2 5 4.X......X. 2 1 2 2 1 7 2 1 */ |