#include <iostream> #include <vector> #include <algorithm> #include <queue> using namespace std; const int M = 2001; const int K = 1e6+1; char mp[M][M]; bool visited[M][M]; int odla[M][M]; int odlb[M][M]; int64_t best[K]; int main() { ios_base::sync_with_stdio(false); int n, m, k; cin >> n >> m >> k; string s; for(int i = 0; i < n; ++i) { cin >> s; for(int j = 0; j < m; ++j) mp[i][j] = s[j]; } queue<pair<int, int> > q; q.push(make_pair(0, 0)); visited[0][0] = true; while(!q.empty()) { pair<int, int> t = q.front(); q.pop(); int x = t.first; int y = t.second; if(x != 0 && !visited[x-1][y] && mp[x-1][y] == '.') { visited[x-1][y] = true; q.push(make_pair(x-1, y)); odla[x-1][y] = odla[x][y]; odlb[x-1][y] = odlb[x][y]+1; } if(y != 0 && !visited[x][y-1] && mp[x][y-1] == '.') { visited[x][y-1] = true; q.push(make_pair(x, y-1)); odla[x][y-1] = odla[x][y]; odlb[x][y-1] = odlb[x][y]+1; } if(x != n-1 && !visited[x+1][y] && mp[x+1][y] == '.') { visited[x+1][y] = true; q.push(make_pair(x+1, y)); odla[x+1][y] = odla[x][y]+1; odlb[x+1][y] = odlb[x][y]; } if(y != m-1 && !visited[x][y+1] && mp[x][y+1] == '.') { visited[x][y+1] = true; q.push(make_pair(x, y+1)); odla[x][y+1] = odla[x][y]+1; odlb[x][y+1] = odlb[x][y]; } } int64_t mini = 1e18; for(int i = 0; i < k; ++i) { int64_t a, b; cin >> a >> b; best[i] = a*odla[n-1][m-1] + b*odlb[n-1][m-1]; if(mini > best[i]) mini = best[i]; } int ct = 0; for(int i = 0; i < k; ++i) { if(best[i] == mini) ++ct; } cout << mini << ' ' << ct << '\n'; }
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 | #include <iostream> #include <vector> #include <algorithm> #include <queue> using namespace std; const int M = 2001; const int K = 1e6+1; char mp[M][M]; bool visited[M][M]; int odla[M][M]; int odlb[M][M]; int64_t best[K]; int main() { ios_base::sync_with_stdio(false); int n, m, k; cin >> n >> m >> k; string s; for(int i = 0; i < n; ++i) { cin >> s; for(int j = 0; j < m; ++j) mp[i][j] = s[j]; } queue<pair<int, int> > q; q.push(make_pair(0, 0)); visited[0][0] = true; while(!q.empty()) { pair<int, int> t = q.front(); q.pop(); int x = t.first; int y = t.second; if(x != 0 && !visited[x-1][y] && mp[x-1][y] == '.') { visited[x-1][y] = true; q.push(make_pair(x-1, y)); odla[x-1][y] = odla[x][y]; odlb[x-1][y] = odlb[x][y]+1; } if(y != 0 && !visited[x][y-1] && mp[x][y-1] == '.') { visited[x][y-1] = true; q.push(make_pair(x, y-1)); odla[x][y-1] = odla[x][y]; odlb[x][y-1] = odlb[x][y]+1; } if(x != n-1 && !visited[x+1][y] && mp[x+1][y] == '.') { visited[x+1][y] = true; q.push(make_pair(x+1, y)); odla[x+1][y] = odla[x][y]+1; odlb[x+1][y] = odlb[x][y]; } if(y != m-1 && !visited[x][y+1] && mp[x][y+1] == '.') { visited[x][y+1] = true; q.push(make_pair(x, y+1)); odla[x][y+1] = odla[x][y]+1; odlb[x][y+1] = odlb[x][y]; } } int64_t mini = 1e18; for(int i = 0; i < k; ++i) { int64_t a, b; cin >> a >> b; best[i] = a*odla[n-1][m-1] + b*odlb[n-1][m-1]; if(mini > best[i]) mini = best[i]; } int ct = 0; for(int i = 0; i < k; ++i) { if(best[i] == mini) ++ct; } cout << mini << ' ' << ct << '\n'; } |