#include<bits/stdc++.h> using namespace std; void enqueueValid(queue<pair<int,int>>& Q, vector<vector<char>>& grid, int x, int y) { if(grid[x][y] == '.') { Q.push({x,y}); grid[x][y] = 'X'; } } int BFS(vector<vector<char>>& grid, int x, int y, int n, int m) { queue<pair<int,int>> Q; Q.push({x,y}); int steps = 0; while(!Q.empty()) { int size = Q.size(); while(size--) { pair<int,int> p = Q.front(); Q.pop(); x = p.first; y = p.second; if(x == n && y == m) { return steps; } enqueueValid(Q, grid, x-1, y); enqueueValid(Q, grid, x+1, y); enqueueValid(Q, grid, x, y-1); enqueueValid(Q, grid, x, y+1); } steps++; } return -1; } int main() { int n, m, k; cin >> n >> m >> k; vector<vector<char>> grid(n+2, vector<char>(m+2)); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> grid[i][j]; } } vector<pair<int,int>> speed(k); for(int i = 0; i < k; i++) { cin >> speed[i].first >> speed[i].second; } int totalSteps = BFS(grid, 1, 1, n, m); int ascSteps = n + m - 2 + (totalSteps - n - m + 2) / 2; int descSteps = totalSteps - ascSteps; long long int resTime = LONG_LONG_MAX; int resCount = 0; for(int i = 0; i < k; i++) { resTime = min(resTime, (long long)speed[i].first * ascSteps + (long long)speed[i].second * descSteps); } for(int i = 0; i < k; i++) { if(((long long)speed[i].first * ascSteps + (long long)speed[i].second * descSteps) == resTime) { resCount++; } } cout << resTime << " " << resCount << endl; }
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 | #include<bits/stdc++.h> using namespace std; void enqueueValid(queue<pair<int,int>>& Q, vector<vector<char>>& grid, int x, int y) { if(grid[x][y] == '.') { Q.push({x,y}); grid[x][y] = 'X'; } } int BFS(vector<vector<char>>& grid, int x, int y, int n, int m) { queue<pair<int,int>> Q; Q.push({x,y}); int steps = 0; while(!Q.empty()) { int size = Q.size(); while(size--) { pair<int,int> p = Q.front(); Q.pop(); x = p.first; y = p.second; if(x == n && y == m) { return steps; } enqueueValid(Q, grid, x-1, y); enqueueValid(Q, grid, x+1, y); enqueueValid(Q, grid, x, y-1); enqueueValid(Q, grid, x, y+1); } steps++; } return -1; } int main() { int n, m, k; cin >> n >> m >> k; vector<vector<char>> grid(n+2, vector<char>(m+2)); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> grid[i][j]; } } vector<pair<int,int>> speed(k); for(int i = 0; i < k; i++) { cin >> speed[i].first >> speed[i].second; } int totalSteps = BFS(grid, 1, 1, n, m); int ascSteps = n + m - 2 + (totalSteps - n - m + 2) / 2; int descSteps = totalSteps - ascSteps; long long int resTime = LONG_LONG_MAX; int resCount = 0; for(int i = 0; i < k; i++) { resTime = min(resTime, (long long)speed[i].first * ascSteps + (long long)speed[i].second * descSteps); } for(int i = 0; i < k; i++) { if(((long long)speed[i].first * ascSteps + (long long)speed[i].second * descSteps) == resTime) { resCount++; } } cout << resTime << " " << resCount << endl; } |