#include<iostream> #include<vector> #include<queue> #include<map> using namespace std; typedef long long ll; const ll INF=999999999999999999; void BFS(vector<vector<char> > &T, vector<vector<ll > > &W,pair<ll ,ll > n) { queue<pair<ll ,ll > > kolejka; kolejka.push(n); W[n.first][n.second]=0; while(!kolejka.empty()) { n=kolejka.front(); kolejka.pop(); pair<ll ,ll > u=n; u.first--; if(W[u.first][u.second]==INF && T[u.first][u.second]=='.') {W[u.first][u.second]=W[n.first][n.second]+1; kolejka.push(u);} u.first+=2; if(W[u.first][u.second]==INF && T[u.first][u.second]=='.') {W[u.first][u.second]=W[n.first][n.second]+1; kolejka.push(u);} u.first--; u.second--; if(W[u.first][u.second]==INF && T[u.first][u.second]=='.') {W[u.first][u.second]=W[n.first][n.second]+1; kolejka.push(u);} u.second+=2; if(W[u.first][u.second]==INF && T[u.first][u.second]=='.') {W[u.first][u.second]=W[n.first][n.second]+1; kolejka.push(u);} } } int main() { ios_base::sync_with_stdio(0); ll n,m,f; cin>>n>>m>>f; vector<vector<char> > T(n+2); vector<vector<ll > > W(n+2); T[0].resize(m+2,'X'); W[0].resize(m+2,INF); for(ll i=1 ; i<=n ; i++) { T[i].resize(m+2); W[i].resize(m+2,INF); for(ll j=0 ; j<=m+1 ; j++) { if(j==0 || j==m+1)T[i][j]='X'; else cin>>T[i][j]; } } T[n+1].resize(m+2,'X'); W[n+1].resize(m+2,INF); BFS(T,W,{1,1}); //cout<<W[n][m]<<endl; ll base=(n-1)+(m-1); ll k=(W[n][m]-base)/2; map<ll ,ll > mapa; ll mini=INF; while(f--) { ll a,b; cin>>a>>b; ll result=base*a+k*(a+b); mini=min(mini,result); // cout<<"result "<<result<<endl; mapa[result]++; } cout<<mini<<" "<<mapa[mini]<<endl; 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 | #include<iostream> #include<vector> #include<queue> #include<map> using namespace std; typedef long long ll; const ll INF=999999999999999999; void BFS(vector<vector<char> > &T, vector<vector<ll > > &W,pair<ll ,ll > n) { queue<pair<ll ,ll > > kolejka; kolejka.push(n); W[n.first][n.second]=0; while(!kolejka.empty()) { n=kolejka.front(); kolejka.pop(); pair<ll ,ll > u=n; u.first--; if(W[u.first][u.second]==INF && T[u.first][u.second]=='.') {W[u.first][u.second]=W[n.first][n.second]+1; kolejka.push(u);} u.first+=2; if(W[u.first][u.second]==INF && T[u.first][u.second]=='.') {W[u.first][u.second]=W[n.first][n.second]+1; kolejka.push(u);} u.first--; u.second--; if(W[u.first][u.second]==INF && T[u.first][u.second]=='.') {W[u.first][u.second]=W[n.first][n.second]+1; kolejka.push(u);} u.second+=2; if(W[u.first][u.second]==INF && T[u.first][u.second]=='.') {W[u.first][u.second]=W[n.first][n.second]+1; kolejka.push(u);} } } int main() { ios_base::sync_with_stdio(0); ll n,m,f; cin>>n>>m>>f; vector<vector<char> > T(n+2); vector<vector<ll > > W(n+2); T[0].resize(m+2,'X'); W[0].resize(m+2,INF); for(ll i=1 ; i<=n ; i++) { T[i].resize(m+2); W[i].resize(m+2,INF); for(ll j=0 ; j<=m+1 ; j++) { if(j==0 || j==m+1)T[i][j]='X'; else cin>>T[i][j]; } } T[n+1].resize(m+2,'X'); W[n+1].resize(m+2,INF); BFS(T,W,{1,1}); //cout<<W[n][m]<<endl; ll base=(n-1)+(m-1); ll k=(W[n][m]-base)/2; map<ll ,ll > mapa; ll mini=INF; while(f--) { ll a,b; cin>>a>>b; ll result=base*a+k*(a+b); mini=min(mini,result); // cout<<"result "<<result<<endl; mapa[result]++; } cout<<mini<<" "<<mapa[mini]<<endl; return 0; } |