#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<ll> vl; typedef vector<vector<ll>> vvl; #define pb push_back #define eb emplace_back #define mp make_pair #define mt make_tuple #define st first #define nd second #define FOR(__VAR, __START, __END) for(int __VAR=__START; __VAR<=__END; __VAR++) #define FORB(__VAR, __START, __END) for(int __VAR=__START; __VAR>=__END; __VAR--) #define FORK(__VAR, __START, __END, __DIFF) for(int __VAR=__START; __VAR<=END; __VAR+=__DIFF) #define all(__VAR) (__VAR).begin(), (__VAR).end() #define rall(__VAR) (__VAR).rbegin(), (__VAR).rend() #define DEBUG(__VAR) cout << #__VAR << ": " << __VAR << endl; template<typename __T1, typename __T2> ostream & operator<<(ostream &out, pair<__T1, __T2> &__VAR) { cout << "[" << __VAR.st << ", " << __VAR.nd << "]"; return out; } template<typename __T> ostream & operator<<(ostream &out, vector<__T> &__VAR) { cout << "["; FOR(i, 0, (int)__VAR.size()-2) cout << __VAR[i] << ", "; if(__VAR.size()>0) cout << __VAR[__VAR.size()-1]; cout << "]" << endl; return out; } const int INF=1e9; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, m, k; cin >> n >> m >> k; vector<vector<bool>> safe(n+2, vector<bool>(m+2, 0)); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) { char type; cin >> type; if(type=='.') safe[i][j]=1; } vector<vector<pll>> g(n*m+1); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) { if(safe[i][j+1]) g[(i-1)*m+j].pb({(i-1)*m+j+1,1LL}); if(safe[i][j-1]) g[(i-1)*m+j].pb({(i-1)*m+j-1,0LL}); if(safe[i+1][j]) g[(i-1)*m+j].pb({i*m+j,1LL}); if(safe[i-1][j]) g[(i-1)*m+j].pb({(i-2)*m+j,0LL}); } vector<ll> dist(n*m+1, INF); dist[n*m]=0; priority_queue<pll,vector<pll>,greater<pll>> que; que.push({0, n*m}); while(!que.empty()) { auto [d, cur]=que.top(); que.pop(); if(d>dist[cur]) continue; for(auto [v,w]:g[cur]) { if(dist[v]>d+w) { dist[v]=min(dist[v],d+w); que.push({d+w,v}); } } } ll result=1e18,num=0, d=dist[1]; while(k--) { ll a, b; cin >> a >> b; ll D=a*(ll)(n+m-2)+(a+b)*d; if(D<result) { result=D; num=1; } else if(result==D) num++; } cout << result << ' ' << num << '\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 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 | #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<ll> vl; typedef vector<vector<ll>> vvl; #define pb push_back #define eb emplace_back #define mp make_pair #define mt make_tuple #define st first #define nd second #define FOR(__VAR, __START, __END) for(int __VAR=__START; __VAR<=__END; __VAR++) #define FORB(__VAR, __START, __END) for(int __VAR=__START; __VAR>=__END; __VAR--) #define FORK(__VAR, __START, __END, __DIFF) for(int __VAR=__START; __VAR<=END; __VAR+=__DIFF) #define all(__VAR) (__VAR).begin(), (__VAR).end() #define rall(__VAR) (__VAR).rbegin(), (__VAR).rend() #define DEBUG(__VAR) cout << #__VAR << ": " << __VAR << endl; template<typename __T1, typename __T2> ostream & operator<<(ostream &out, pair<__T1, __T2> &__VAR) { cout << "[" << __VAR.st << ", " << __VAR.nd << "]"; return out; } template<typename __T> ostream & operator<<(ostream &out, vector<__T> &__VAR) { cout << "["; FOR(i, 0, (int)__VAR.size()-2) cout << __VAR[i] << ", "; if(__VAR.size()>0) cout << __VAR[__VAR.size()-1]; cout << "]" << endl; return out; } const int INF=1e9; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, m, k; cin >> n >> m >> k; vector<vector<bool>> safe(n+2, vector<bool>(m+2, 0)); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) { char type; cin >> type; if(type=='.') safe[i][j]=1; } vector<vector<pll>> g(n*m+1); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) { if(safe[i][j+1]) g[(i-1)*m+j].pb({(i-1)*m+j+1,1LL}); if(safe[i][j-1]) g[(i-1)*m+j].pb({(i-1)*m+j-1,0LL}); if(safe[i+1][j]) g[(i-1)*m+j].pb({i*m+j,1LL}); if(safe[i-1][j]) g[(i-1)*m+j].pb({(i-2)*m+j,0LL}); } vector<ll> dist(n*m+1, INF); dist[n*m]=0; priority_queue<pll,vector<pll>,greater<pll>> que; que.push({0, n*m}); while(!que.empty()) { auto [d, cur]=que.top(); que.pop(); if(d>dist[cur]) continue; for(auto [v,w]:g[cur]) { if(dist[v]>d+w) { dist[v]=min(dist[v],d+w); que.push({d+w,v}); } } } ll result=1e18,num=0, d=dist[1]; while(k--) { ll a, b; cin >> a >> b; ll D=a*(ll)(n+m-2)+(a+b)*d; if(D<result) { result=D; num=1; } else if(result==D) num++; } cout << result << ' ' << num << '\n'; return 0; } |