#include <bits/stdc++.h> using namespace std; int *odl; long long n, m, k, d, up, a, b, mini=LONG_LONG_MAX, suma; char *mapa; vector<vector<int> > v; void bfs(int src) { queue <int> S; S.push(src); odl[src]=0; while(!S.empty()) { int u=S.front(); S.pop(); for(int i=0;i<v[u].size();i++) { if(odl[v[u][i]]>odl[u]+1) { odl[v[u][i]]=odl[u]+1; S.push(v[u][i]); } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>k; mapa=new char[n*m]; odl=new int[n*m]; for(int i=0;i<n;i++) { for(int u=0;u<m;u++) { cin>>mapa[i*m+u]; v.push_back({}); odl[i*m+u]=INT_MAX; } } for(int i=0;i<n;i++) { for(int u=0;u<m;u++) { if(mapa[i*m+u]!='X') { if(i!=0) if(mapa[(i-1)*m+u]!='X')v[i*m+u].push_back((i-1)*m+u); if(u!=0) if(mapa[i*m+u-1]!='X')v[i*m+u].push_back(i*m+u-1); if(i!=n-1) if(mapa[(i+1)*m+u]!='X')v[i*m+u].push_back((i+1)*m+u); if(u!=m-1) if(mapa[i*m+u+1]!='X')v[i*m+u].push_back(i*m+u+1); } } } bfs(0); up=n-1+m-1; d=odl[n*m-1]-up; d/=2; up+=d; for(int i=0;i<k;i++) { cin>>a>>b; if((b*d)+(a*up)<mini) { suma=1; mini=(b*d)+(a*up); } else if((b*d)+(a*up)==mini) { suma++; } } /*cout<<endl; for(int i=0;i<n;i++) { for(int u=0;u<m;u++) { if(odl[i*m+u]==INT_MAX)cout<<-1<<' '; else cout<<odl[i*m+u]<<' '; } cout<<endl; }*/ cout<<mini<<' '<<suma<<endl; //cout<<odl[n*m-1]<<endl; delete [] mapa; delete [] odl; 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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 | #include <bits/stdc++.h> using namespace std; int *odl; long long n, m, k, d, up, a, b, mini=LONG_LONG_MAX, suma; char *mapa; vector<vector<int> > v; void bfs(int src) { queue <int> S; S.push(src); odl[src]=0; while(!S.empty()) { int u=S.front(); S.pop(); for(int i=0;i<v[u].size();i++) { if(odl[v[u][i]]>odl[u]+1) { odl[v[u][i]]=odl[u]+1; S.push(v[u][i]); } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>k; mapa=new char[n*m]; odl=new int[n*m]; for(int i=0;i<n;i++) { for(int u=0;u<m;u++) { cin>>mapa[i*m+u]; v.push_back({}); odl[i*m+u]=INT_MAX; } } for(int i=0;i<n;i++) { for(int u=0;u<m;u++) { if(mapa[i*m+u]!='X') { if(i!=0) if(mapa[(i-1)*m+u]!='X')v[i*m+u].push_back((i-1)*m+u); if(u!=0) if(mapa[i*m+u-1]!='X')v[i*m+u].push_back(i*m+u-1); if(i!=n-1) if(mapa[(i+1)*m+u]!='X')v[i*m+u].push_back((i+1)*m+u); if(u!=m-1) if(mapa[i*m+u+1]!='X')v[i*m+u].push_back(i*m+u+1); } } } bfs(0); up=n-1+m-1; d=odl[n*m-1]-up; d/=2; up+=d; for(int i=0;i<k;i++) { cin>>a>>b; if((b*d)+(a*up)<mini) { suma=1; mini=(b*d)+(a*up); } else if((b*d)+(a*up)==mini) { suma++; } } /*cout<<endl; for(int i=0;i<n;i++) { for(int u=0;u<m;u++) { if(odl[i*m+u]==INT_MAX)cout<<-1<<' '; else cout<<odl[i*m+u]<<' '; } cout<<endl; }*/ cout<<mini<<' '<<suma<<endl; //cout<<odl[n*m-1]<<endl; delete [] mapa; delete [] odl; return 0; } |