#include <bits/stdc++.h> #define IOSTREAM_BOOST true using namespace std; template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "{"; if (!vec.empty()) os << vec[0]; for (int i = 1; i < vec.size(); i++) os << ", " << vec[i]; os << "}"; return os; } int n, m, k; int dist[2005][2005]; bool blockMap[2005][2005]; deque<pair<int, int>> q; bool isValid(pair<int, int> coords){ if(coords.first < 0 || coords.first >= n) return false; if(coords.second < 0 || coords.second >= m) return false; if(blockMap[coords.first][coords.second]) return false; return true; } void bfs(){ for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) dist[i][j] = INT_MAX; dist[0][0] = 0; q.push_back({0, 0}); while(!q.empty()){ pair<int, int> v = q.front(); q.pop_front(); for(int dx = -1; dx <= 1; dx++) for(int dy = -1; dy <= 1; dy++){ if(!dx && !dy) continue; if(dx && dy) continue; pair<int, int> newCoords = {v.first + dx, v.second + dy}; if(!isValid(newCoords)) continue; int weight = (dx == -1 || dy == -1 ? 1 : 0); if(dist[newCoords.first][newCoords.second] > dist[v.first][v.second] + weight){ dist[newCoords.first][newCoords.second] = dist[v.first][v.second] + weight; if(weight == 0) q.push_front(newCoords); else q.push_back(newCoords); } } } } string tstr; long long minv = LLONG_MAX; int minc = 0; int main() { #if IOSTREAM_BOOST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #endif cin >> n >> m >> k; for(int i = 0; i < n; i++){ cin >> tstr; for(int j = 0; j < m; j++) blockMap[i][j] = (tstr[j] == 'X'); } bfs(); for(int i = 0; i < k; i++){ long long a, b; cin >> a >> b; long long v = a * (n + m - 2 + dist[n - 1][m - 1]) + b * dist[n - 1][m - 1]; if(minv > v) minv = v, minc = 0; if(minv == v) minc++; } cout << minv << " " << minc << "\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 68 69 70 71 72 73 74 75 76 77 | #include <bits/stdc++.h> #define IOSTREAM_BOOST true using namespace std; template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "{"; if (!vec.empty()) os << vec[0]; for (int i = 1; i < vec.size(); i++) os << ", " << vec[i]; os << "}"; return os; } int n, m, k; int dist[2005][2005]; bool blockMap[2005][2005]; deque<pair<int, int>> q; bool isValid(pair<int, int> coords){ if(coords.first < 0 || coords.first >= n) return false; if(coords.second < 0 || coords.second >= m) return false; if(blockMap[coords.first][coords.second]) return false; return true; } void bfs(){ for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) dist[i][j] = INT_MAX; dist[0][0] = 0; q.push_back({0, 0}); while(!q.empty()){ pair<int, int> v = q.front(); q.pop_front(); for(int dx = -1; dx <= 1; dx++) for(int dy = -1; dy <= 1; dy++){ if(!dx && !dy) continue; if(dx && dy) continue; pair<int, int> newCoords = {v.first + dx, v.second + dy}; if(!isValid(newCoords)) continue; int weight = (dx == -1 || dy == -1 ? 1 : 0); if(dist[newCoords.first][newCoords.second] > dist[v.first][v.second] + weight){ dist[newCoords.first][newCoords.second] = dist[v.first][v.second] + weight; if(weight == 0) q.push_front(newCoords); else q.push_back(newCoords); } } } } string tstr; long long minv = LLONG_MAX; int minc = 0; int main() { #if IOSTREAM_BOOST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #endif cin >> n >> m >> k; for(int i = 0; i < n; i++){ cin >> tstr; for(int j = 0; j < m; j++) blockMap[i][j] = (tstr[j] == 'X'); } bfs(); for(int i = 0; i < k; i++){ long long a, b; cin >> a >> b; long long v = a * (n + m - 2 + dist[n - 1][m - 1]) + b * dist[n - 1][m - 1]; if(minv > v) minv = v, minc = 0; if(minv == v) minc++; } cout << minv << " " << minc << "\n"; return 0; } |