#include <bits/stdc++.h> using namespace std; long long wyn=40000000000000, akt, odl[4000005], x; vector <pair <int, int> > G[4000005]; int n, m, k, lwyn, a, b; char c[4000005]; queue <int> Q; int main(){ ios_base::sync_with_stdio(0); cout.tie(NULL); cin.tie(NULL); cin>>n>>m>>k; for (int i=1; i<=n; i++){ for (int j=1; j<=m; j++){ cin>>c[m*(i-1)+j]; } } for (int i=1; i<=n; i++){ for (int j=1; j<=m; j++){ if(c[m*(i-1)+j]=='.'){ if (j<m&&c[m*(i-1)+j+1]=='.'){ G[m*(i-1)+j].push_back(make_pair(m*(i-1)+j+1, 1)); } if (i<n&&c[m*i+j]=='.'){ G[m*(i-1)+j].push_back(make_pair(m*i+j, 1)); } if (i>1&&c[m*(i-2)+j]=='.'){ G[m*(i-1)+j].push_back(make_pair(m*(i-2)+j, 0)); } if (j>1&&c[m*(i-1)+j-1]=='.'){ G[m*(i-1)+j].push_back(make_pair(m*(i-1)+j-1, 0)); } } odl[m*(i-1)+j]=40000000000000; } } for (int i=1; i<=k; i++){ cin>>a>>b; Q.push(1); odl[1]=0; while (!Q.empty()){ x=Q.front(); Q.pop(); for (int i=0; i<G[x].size(); i++){ if (G[x][i].second==1&&odl[x]+a<odl[G[x][i].first]){ odl[G[x][i].first]=odl[x]+a; Q.push(G[x][i].first); } if (G[x][i].second==0&&odl[x]+b<odl[G[x][i].first]){ odl[G[x][i].first]=odl[x]+b; Q.push(G[x][i].first); } } } if (odl[m*n]<wyn){ wyn=odl[m*n]; } if (odl[m*n]==wyn){ lwyn++; } for (int i=1; i<=n; i++){ for (int j=1; j<=m; j++){ odl[m*(i-1)+j]=40000000000000; } } } cout<<wyn<<" "<<lwyn; 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 | #include <bits/stdc++.h> using namespace std; long long wyn=40000000000000, akt, odl[4000005], x; vector <pair <int, int> > G[4000005]; int n, m, k, lwyn, a, b; char c[4000005]; queue <int> Q; int main(){ ios_base::sync_with_stdio(0); cout.tie(NULL); cin.tie(NULL); cin>>n>>m>>k; for (int i=1; i<=n; i++){ for (int j=1; j<=m; j++){ cin>>c[m*(i-1)+j]; } } for (int i=1; i<=n; i++){ for (int j=1; j<=m; j++){ if(c[m*(i-1)+j]=='.'){ if (j<m&&c[m*(i-1)+j+1]=='.'){ G[m*(i-1)+j].push_back(make_pair(m*(i-1)+j+1, 1)); } if (i<n&&c[m*i+j]=='.'){ G[m*(i-1)+j].push_back(make_pair(m*i+j, 1)); } if (i>1&&c[m*(i-2)+j]=='.'){ G[m*(i-1)+j].push_back(make_pair(m*(i-2)+j, 0)); } if (j>1&&c[m*(i-1)+j-1]=='.'){ G[m*(i-1)+j].push_back(make_pair(m*(i-1)+j-1, 0)); } } odl[m*(i-1)+j]=40000000000000; } } for (int i=1; i<=k; i++){ cin>>a>>b; Q.push(1); odl[1]=0; while (!Q.empty()){ x=Q.front(); Q.pop(); for (int i=0; i<G[x].size(); i++){ if (G[x][i].second==1&&odl[x]+a<odl[G[x][i].first]){ odl[G[x][i].first]=odl[x]+a; Q.push(G[x][i].first); } if (G[x][i].second==0&&odl[x]+b<odl[G[x][i].first]){ odl[G[x][i].first]=odl[x]+b; Q.push(G[x][i].first); } } } if (odl[m*n]<wyn){ wyn=odl[m*n]; } if (odl[m*n]==wyn){ lwyn++; } for (int i=1; i<=n; i++){ for (int j=1; j<=m; j++){ odl[m*(i-1)+j]=40000000000000; } } } cout<<wyn<<" "<<lwyn; return 0; } |