#include <bits/stdc++.h> using namespace std; #define PII pair<int,int> int arr[2005][2005]; int dist[2005][2005]; deque<PII> Q; void dijkstra() { dist[1][1]=0; Q.push_front({1,1}); while(!Q.empty()) { PII u=Q.front(); Q.pop_front(); if(dist[u.first+1][u.second]>dist[u.first][u.second]&&arr[u.first+1][u.second]==0) { dist[u.first+1][u.second]=dist[u.first][u.second]; Q.push_front({u.first+1,u.second}); } if(dist[u.first-1][u.second]>dist[u.first][u.second]+1&&arr[u.first-1][u.second]==0) { dist[u.first-1][u.second]=dist[u.first][u.second]+1; Q.push_back({u.first-1,u.second}); } if(dist[u.first][u.second+1]>dist[u.first][u.second]&&arr[u.first][u.second+1]==0) { dist[u.first][u.second+1]=dist[u.first][u.second]; Q.push_front({u.first,u.second+1}); } if(dist[u.first][u.second-1]>dist[u.first][u.second]+1&&arr[u.first][u.second-1]==0) { dist[u.first][u.second-1]=dist[u.first][u.second]+1; Q.push_back({u.first,u.second-1}); } } } int main() { ios_base::sync_with_stdio(0); int n,m,k; cin>>n>>m>>k; for(int i=0;i<=n+1;i++)for(int j=0;j<=m+1;j++)arr[i][j]=1, dist[i][j]=1e9; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) { char c; cin>>c; if(c=='.')arr[i][j]=0; } dijkstra(); long long res=1e18; int cnt=0; while(k--) { long long a,b; cin>>a>>b; long long tmp=(n+m-2)*a+dist[n][m]*(a+b); if(tmp==res)cnt++; else if(tmp<res)res=tmp, cnt=1; } cout<<res<<" "<<cnt<<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 | #include <bits/stdc++.h> using namespace std; #define PII pair<int,int> int arr[2005][2005]; int dist[2005][2005]; deque<PII> Q; void dijkstra() { dist[1][1]=0; Q.push_front({1,1}); while(!Q.empty()) { PII u=Q.front(); Q.pop_front(); if(dist[u.first+1][u.second]>dist[u.first][u.second]&&arr[u.first+1][u.second]==0) { dist[u.first+1][u.second]=dist[u.first][u.second]; Q.push_front({u.first+1,u.second}); } if(dist[u.first-1][u.second]>dist[u.first][u.second]+1&&arr[u.first-1][u.second]==0) { dist[u.first-1][u.second]=dist[u.first][u.second]+1; Q.push_back({u.first-1,u.second}); } if(dist[u.first][u.second+1]>dist[u.first][u.second]&&arr[u.first][u.second+1]==0) { dist[u.first][u.second+1]=dist[u.first][u.second]; Q.push_front({u.first,u.second+1}); } if(dist[u.first][u.second-1]>dist[u.first][u.second]+1&&arr[u.first][u.second-1]==0) { dist[u.first][u.second-1]=dist[u.first][u.second]+1; Q.push_back({u.first,u.second-1}); } } } int main() { ios_base::sync_with_stdio(0); int n,m,k; cin>>n>>m>>k; for(int i=0;i<=n+1;i++)for(int j=0;j<=m+1;j++)arr[i][j]=1, dist[i][j]=1e9; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) { char c; cin>>c; if(c=='.')arr[i][j]=0; } dijkstra(); long long res=1e18; int cnt=0; while(k--) { long long a,b; cin>>a>>b; long long tmp=(n+m-2)*a+dist[n][m]*(a+b); if(tmp==res)cnt++; else if(tmp<res)res=tmp, cnt=1; } cout<<res<<" "<<cnt<<endl; } |