#include <bits/stdc++.h> #include <deque> using namespace std; const int inf = 999999999; const int s = 2009; int tab[s][s]; int dis[s][s]; deque<pair<int,int>> q; /* void DFS1(int x, int y, int n, int m, int t) { if(dis[x][y] != inf) return; dis[x][y] = t; if(x > 0) { if(tab[x - 1][y]) { DFS1(x - 1, y, n, m, t + 1); } } if(y > 0) { if(tab[x][y - 1]) { DFS1(x, y - 1, n, m, t + 1); } } if(x < n - 1) { if(tab[x + 1][y]) { DFS1(x + 1, y, n, m, t + 1); } } if(y < m - 1) { if(tab[x][y + 1]) { DFS1(x, y + 1, n, m, t + 1); } } return; }*/ void distance(int n, int m) { deque<pair<int, int>> q; q.push_back(make_pair(0, 0)); dis[0][0] = 0; while(!q.empty()) { pair<int, int> p = q.front(); q.pop_front(); int cdist = dis[p.first][p.second]; if (p.first > 0) { if (tab[p.first - 1][p.second] && (dis[p.first - 1][p.second] == inf)) { dis[p.first - 1][p.second] = cdist + 1; q.push_back(make_pair(p.first - 1, p.second)); } } if (p.first < n - 1) { if (tab[p.first + 1][p.second] && (dis[p.first + 1][p.second] == inf)) { dis[p.first + 1][p.second] = cdist + 1; q.push_back(make_pair(p.first + 1, p.second)); } } if (p.second > 0) { if (tab[p.first][p.second - 1] && (dis[p.first][p.second - 1] == inf)) { dis[p.first][p.second - 1] = cdist + 1; q.push_back(make_pair(p.first, p.second - 1)); } } if (p.second < m - 1) { if (tab[p.first][p.second + 1] && (dis[p.first][p.second + 1] == inf)) { dis[p.first][p.second + 1] = cdist + 1; q.push_back(make_pair(p.first, p.second + 1)); } } } } void print(int n, int m) { for(int i = 0; i < n; i ++) { for(int k = 0; k < m; k ++) { cout << tab[i][k] << " "; } cout << "\n"; } cout << "\n"; for(int i = 0; i < n; i ++) { for(int k = 0; k < m; k ++) { cout << dis[i][k] << " "; } cout << "\n"; } } int main() { std::ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m, z; cin >> n >> m >> z; for(int i = 0; i < n; i ++) { for(int k = 0; k < m; k ++) { char x; cin >> x; if(x == '.') tab[i][k] = true; else tab[i][k] = false; } } for(int i = 0; i < n; i ++) { for(int k = 0; k < m; k ++) dis[i][k] = inf; } //DFS1(0, 0, n, m, 0); distance(n, m); //print(n,m); int dlug = dis[n - 1][m - 1]; long long x = n + m - 2 + (dlug - (n + m - 2)) / 2, y = dlug - x; long long best = 999999999999999999, ile = 0; for(int i = 0; i < z; i ++) { long long a, b; cin >> a >> b; if(a * x + b * y < best) { best = a * x + b * y; ile = 1; } else if(a * x + b * y == best) ile ++; } cout << best << ' ' << ile; 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 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 | #include <bits/stdc++.h> #include <deque> using namespace std; const int inf = 999999999; const int s = 2009; int tab[s][s]; int dis[s][s]; deque<pair<int,int>> q; /* void DFS1(int x, int y, int n, int m, int t) { if(dis[x][y] != inf) return; dis[x][y] = t; if(x > 0) { if(tab[x - 1][y]) { DFS1(x - 1, y, n, m, t + 1); } } if(y > 0) { if(tab[x][y - 1]) { DFS1(x, y - 1, n, m, t + 1); } } if(x < n - 1) { if(tab[x + 1][y]) { DFS1(x + 1, y, n, m, t + 1); } } if(y < m - 1) { if(tab[x][y + 1]) { DFS1(x, y + 1, n, m, t + 1); } } return; }*/ void distance(int n, int m) { deque<pair<int, int>> q; q.push_back(make_pair(0, 0)); dis[0][0] = 0; while(!q.empty()) { pair<int, int> p = q.front(); q.pop_front(); int cdist = dis[p.first][p.second]; if (p.first > 0) { if (tab[p.first - 1][p.second] && (dis[p.first - 1][p.second] == inf)) { dis[p.first - 1][p.second] = cdist + 1; q.push_back(make_pair(p.first - 1, p.second)); } } if (p.first < n - 1) { if (tab[p.first + 1][p.second] && (dis[p.first + 1][p.second] == inf)) { dis[p.first + 1][p.second] = cdist + 1; q.push_back(make_pair(p.first + 1, p.second)); } } if (p.second > 0) { if (tab[p.first][p.second - 1] && (dis[p.first][p.second - 1] == inf)) { dis[p.first][p.second - 1] = cdist + 1; q.push_back(make_pair(p.first, p.second - 1)); } } if (p.second < m - 1) { if (tab[p.first][p.second + 1] && (dis[p.first][p.second + 1] == inf)) { dis[p.first][p.second + 1] = cdist + 1; q.push_back(make_pair(p.first, p.second + 1)); } } } } void print(int n, int m) { for(int i = 0; i < n; i ++) { for(int k = 0; k < m; k ++) { cout << tab[i][k] << " "; } cout << "\n"; } cout << "\n"; for(int i = 0; i < n; i ++) { for(int k = 0; k < m; k ++) { cout << dis[i][k] << " "; } cout << "\n"; } } int main() { std::ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m, z; cin >> n >> m >> z; for(int i = 0; i < n; i ++) { for(int k = 0; k < m; k ++) { char x; cin >> x; if(x == '.') tab[i][k] = true; else tab[i][k] = false; } } for(int i = 0; i < n; i ++) { for(int k = 0; k < m; k ++) dis[i][k] = inf; } //DFS1(0, 0, n, m, 0); distance(n, m); //print(n,m); int dlug = dis[n - 1][m - 1]; long long x = n + m - 2 + (dlug - (n + m - 2)) / 2, y = dlug - x; long long best = 999999999999999999, ile = 0; for(int i = 0; i < z; i ++) { long long a, b; cin >> a >> b; if(a * x + b * y < best) { best = a * x + b * y; ile = 1; } else if(a * x + b * y == best) ile ++; } cout << best << ' ' << ile; return 0; } |