#include <bits/stdc++.h> using namespace std; long long n,m,k,a,b; vector<pair<int,int> >V[4000100]; char c; int mapa[2010][2010]; long long dp[4000100]; bool odwiedzone[4000100]; long long minio=400000000000000000,radzio; deque<int>Q; int v; long long g,d; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; for(int i=0; i<n; i++){ for(int j=1; j<=m; j++){ cin >> c; if(c=='.')mapa[i][j]=1; } } for(int i=0; i<n; i++){ for(int j=1; j<=m; j++){ if(mapa[i][j]==1){ if(j<m&&mapa[i][j+1]==1){ V[i*m+j].push_back(make_pair((i*m+j+1),1)); V[i*m+j+1].push_back(make_pair(i*m+j,0)); } if(i<n-1&&mapa[i+1][j]==1){ V[i*m+j].push_back(make_pair(((i+1)*m+j),1)); V[(i+1)*m+j].push_back(make_pair((i*m+j),0)); } } } } for(int i=2; i<=m*n; i++){ dp[i]=404000000000; } Q.push_front(1); while(!Q.empty()){ v=Q.front(); Q.pop_front(); for(unsigned int i=0; i<V[v].size(); i++){ int nod=V[v][i].first; if(dp[v]<dp[nod]-V[v][i].second){ dp[nod]=dp[v]+V[v][i].second; if(V[v][i].second==1){ Q.push_back(nod); } else Q.push_front(nod); } } } g=dp[m*n]; d=g-m-n+2; for(int i=0; i<k; i++){ cin >> a >> b; if(a*g+d*b<minio){ radzio=1; minio=a*g+b*d; } else if(a*g+b*d==minio){ radzio++; } } cout << minio << ' ' << radzio; 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 | #include <bits/stdc++.h> using namespace std; long long n,m,k,a,b; vector<pair<int,int> >V[4000100]; char c; int mapa[2010][2010]; long long dp[4000100]; bool odwiedzone[4000100]; long long minio=400000000000000000,radzio; deque<int>Q; int v; long long g,d; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; for(int i=0; i<n; i++){ for(int j=1; j<=m; j++){ cin >> c; if(c=='.')mapa[i][j]=1; } } for(int i=0; i<n; i++){ for(int j=1; j<=m; j++){ if(mapa[i][j]==1){ if(j<m&&mapa[i][j+1]==1){ V[i*m+j].push_back(make_pair((i*m+j+1),1)); V[i*m+j+1].push_back(make_pair(i*m+j,0)); } if(i<n-1&&mapa[i+1][j]==1){ V[i*m+j].push_back(make_pair(((i+1)*m+j),1)); V[(i+1)*m+j].push_back(make_pair((i*m+j),0)); } } } } for(int i=2; i<=m*n; i++){ dp[i]=404000000000; } Q.push_front(1); while(!Q.empty()){ v=Q.front(); Q.pop_front(); for(unsigned int i=0; i<V[v].size(); i++){ int nod=V[v][i].first; if(dp[v]<dp[nod]-V[v][i].second){ dp[nod]=dp[v]+V[v][i].second; if(V[v][i].second==1){ Q.push_back(nod); } else Q.push_front(nod); } } } g=dp[m*n]; d=g-m-n+2; for(int i=0; i<k; i++){ cin >> a >> b; if(a*g+d*b<minio){ radzio=1; minio=a*g+b*d; } else if(a*g+b*d==minio){ radzio++; } } cout << minio << ' ' << radzio; return 0; } |