#include<bits/stdc++.h> typedef long long ll; typedef std::pair<ll, ll> pll; typedef std::pair<int, int> pii; template <typename T1, typename T2, typename T3> struct triple { triple (T1 a, T2 b, T3 c){first=a; second=b; third=c;} T1 first; T2 second; T3 third; }; typedef triple<int, int, int> tiii; #define all(x) (x).begin(),(x).end() #define debug std::cout<<"ok"<<std::endl const ll INF=1e18; const std::vector<pii> translates={{1,0}, {0,1}, {-1, 0}, {0, -1}}; main () { int n,m,k; std::cin>>n>>m>>k; std::vector<std::vector<int>> G(n+2, std::vector<int> (m+2, 0)); std::vector<std::vector<pii>> D(n+2, std::vector<pii> (m+2, {-1,-1})); for (int i=0; i<n; i++) { std::string S; std::cin>>S; for (int j=0; j<m; j++) if (S[j]=='.') G[i+1][j+1]=1; } std::queue<pii> Q; Q.push({1,1}); D[1][1]={0,0}; while(Q.size()) { for (auto a:translates) { if (G[Q.front().first+a.first][Q.front().second+a.second] && D[Q.front().first+a.first][Q.front().second+a.second].first<0) { D[Q.front().first+a.first][Q.front().second+a.second]=D[Q.front().first][Q.front().second]; if (a.first>0 || a.second>0) D[Q.front().first+a.first][Q.front().second+a.second].first++; else D[Q.front().first+a.first][Q.front().second+a.second].second++; Q.push({Q.front().first+a.first,Q.front().second+a.second}); } } Q.pop(); } long long W=INF; long long i=0; while(k--) { ll a,b; std::cin>>a>>b; long long T=a*D[n][m].first+b*D[n][m].second; if (T<W) { W=T; i=1; } else if (T==W) i++; } std::cout<<W<<' '<<i<<std::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 69 70 71 72 73 74 | #include<bits/stdc++.h> typedef long long ll; typedef std::pair<ll, ll> pll; typedef std::pair<int, int> pii; template <typename T1, typename T2, typename T3> struct triple { triple (T1 a, T2 b, T3 c){first=a; second=b; third=c;} T1 first; T2 second; T3 third; }; typedef triple<int, int, int> tiii; #define all(x) (x).begin(),(x).end() #define debug std::cout<<"ok"<<std::endl const ll INF=1e18; const std::vector<pii> translates={{1,0}, {0,1}, {-1, 0}, {0, -1}}; main () { int n,m,k; std::cin>>n>>m>>k; std::vector<std::vector<int>> G(n+2, std::vector<int> (m+2, 0)); std::vector<std::vector<pii>> D(n+2, std::vector<pii> (m+2, {-1,-1})); for (int i=0; i<n; i++) { std::string S; std::cin>>S; for (int j=0; j<m; j++) if (S[j]=='.') G[i+1][j+1]=1; } std::queue<pii> Q; Q.push({1,1}); D[1][1]={0,0}; while(Q.size()) { for (auto a:translates) { if (G[Q.front().first+a.first][Q.front().second+a.second] && D[Q.front().first+a.first][Q.front().second+a.second].first<0) { D[Q.front().first+a.first][Q.front().second+a.second]=D[Q.front().first][Q.front().second]; if (a.first>0 || a.second>0) D[Q.front().first+a.first][Q.front().second+a.second].first++; else D[Q.front().first+a.first][Q.front().second+a.second].second++; Q.push({Q.front().first+a.first,Q.front().second+a.second}); } } Q.pop(); } long long W=INF; long long i=0; while(k--) { ll a,b; std::cin>>a>>b; long long T=a*D[n][m].first+b*D[n][m].second; if (T<W) { W=T; i=1; } else if (T==W) i++; } std::cout<<W<<' '<<i<<std::endl; } |