//Author: Piotr Zielinski #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 2005; vector<vector<char>> in(N, vector<char> (N, 'X')); vector<vector<PII>> dist(N, vector<PII> (N, PII (-1, -1))); void add(queue<PII> &q, int x, int y, PII d) { if(dist[x][y].first == -1 && in[x][y] != 'X') { q.push({x, y}); dist[x][y] = d; } } int main() { ios::sync_with_stdio(0); cin.tie(nullptr); int n, m, k; cin >> n >> m >> k; for(int i = 1;i <= n;++i) { for(int j = 1;j <= m;++j) { cin >> in[i][j]; } } queue<PII> Q; Q.push({1, 1}); dist[1][1] = {0, 0}; while(!Q.empty()) { PII cur = Q.front(); Q.pop(); add(Q, cur.first + 1, cur.second, {dist[cur.first][cur.second].first + 1, dist[cur.first][cur.second].second}); add(Q, cur.first - 1, cur.second, {dist[cur.first][cur.second].first, dist[cur.first][cur.second].second + 1}); add(Q, cur.first, cur.second + 1, {dist[cur.first][cur.second].first + 1, dist[cur.first][cur.second].second}); add(Q, cur.first, cur.second - 1, {dist[cur.first][cur.second].first, dist[cur.first][cur.second].second + 1}); } // cout << dist[n][m].first << " " << dist[n][m].second << endl; LL a, b; LL res = 1e18, cRes = 0, tRes; while(k --> 0) { cin >> a >> b; tRes = a * dist[n][m].first + b * dist[n][m].second; if(tRes < res) { res = tRes; cRes = 1; } else if(tRes == res) ++cRes; } cout << res << " " << cRes << "\n"; 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 | //Author: Piotr Zielinski #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 2005; vector<vector<char>> in(N, vector<char> (N, 'X')); vector<vector<PII>> dist(N, vector<PII> (N, PII (-1, -1))); void add(queue<PII> &q, int x, int y, PII d) { if(dist[x][y].first == -1 && in[x][y] != 'X') { q.push({x, y}); dist[x][y] = d; } } int main() { ios::sync_with_stdio(0); cin.tie(nullptr); int n, m, k; cin >> n >> m >> k; for(int i = 1;i <= n;++i) { for(int j = 1;j <= m;++j) { cin >> in[i][j]; } } queue<PII> Q; Q.push({1, 1}); dist[1][1] = {0, 0}; while(!Q.empty()) { PII cur = Q.front(); Q.pop(); add(Q, cur.first + 1, cur.second, {dist[cur.first][cur.second].first + 1, dist[cur.first][cur.second].second}); add(Q, cur.first - 1, cur.second, {dist[cur.first][cur.second].first, dist[cur.first][cur.second].second + 1}); add(Q, cur.first, cur.second + 1, {dist[cur.first][cur.second].first + 1, dist[cur.first][cur.second].second}); add(Q, cur.first, cur.second - 1, {dist[cur.first][cur.second].first, dist[cur.first][cur.second].second + 1}); } // cout << dist[n][m].first << " " << dist[n][m].second << endl; LL a, b; LL res = 1e18, cRes = 0, tRes; while(k --> 0) { cin >> a >> b; tRes = a * dist[n][m].first + b * dist[n][m].second; if(tRes < res) { res = tRes; cRes = 1; } else if(tRes == res) ++cRes; } cout << res << " " << cRes << "\n"; return 0; } |