#include <iostream> #include <vector> #include <queue> #include <string> typedef long long int ll; struct entry { bool blocked=false; int dist=-1; }; int n, m; std::vector< std::vector<entry> > map; struct point { int i; int j; }; std::queue<point> q; void visit(const point& p,int pdist) { if(p.i<0||p.i>=n)return; if(p.j<0||p.j>=m)return; if(map[p.i][p.j].blocked)return; if(map[p.i][p.j].dist!=-1)return; map[p.i][p.j].dist=pdist+1; q.push(p); } int calc_x() { q.push({0,0}); map[0][0].dist=0; while(!q.empty()) { point p=q.front(); q.pop(); int pdist=map[p.i][p.j].dist; visit({p.i+1,p.j},pdist); visit({p.i-1,p.j},pdist); visit({p.i,p.j+1},pdist); visit({p.i,p.j-1},pdist); } int dist=map.back().back().dist; return (dist-(n+m-2))/2; } int main() { int k; std::cin>>n>>m>>k; map.resize(n); for(int i=0;i<n;++i) { map[i].resize(m); std::string s; std::cin>>s; for(int j=0;j<m;++j) if(s[j]=='X') map[i][j].blocked=true; } int x=calc_x(); int cnt=0; ll best=std::numeric_limits<ll>::max(); for(int i=0;i<k;++i) { ll a,b; std::cin>>a>>b; ll i_best=(n+m-2)*a+x*(a+b); if(!cnt||i_best<best) { cnt=1; best=i_best; } else if(i_best==best) ++cnt; } std::cout<<best<<" "<<cnt; 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 | #include <iostream> #include <vector> #include <queue> #include <string> typedef long long int ll; struct entry { bool blocked=false; int dist=-1; }; int n, m; std::vector< std::vector<entry> > map; struct point { int i; int j; }; std::queue<point> q; void visit(const point& p,int pdist) { if(p.i<0||p.i>=n)return; if(p.j<0||p.j>=m)return; if(map[p.i][p.j].blocked)return; if(map[p.i][p.j].dist!=-1)return; map[p.i][p.j].dist=pdist+1; q.push(p); } int calc_x() { q.push({0,0}); map[0][0].dist=0; while(!q.empty()) { point p=q.front(); q.pop(); int pdist=map[p.i][p.j].dist; visit({p.i+1,p.j},pdist); visit({p.i-1,p.j},pdist); visit({p.i,p.j+1},pdist); visit({p.i,p.j-1},pdist); } int dist=map.back().back().dist; return (dist-(n+m-2))/2; } int main() { int k; std::cin>>n>>m>>k; map.resize(n); for(int i=0;i<n;++i) { map[i].resize(m); std::string s; std::cin>>s; for(int j=0;j<m;++j) if(s[j]=='X') map[i][j].blocked=true; } int x=calc_x(); int cnt=0; ll best=std::numeric_limits<ll>::max(); for(int i=0;i<k;++i) { ll a,b; std::cin>>a>>b; ll i_best=(n+m-2)*a+x*(a+b); if(!cnt||i_best<best) { cnt=1; best=i_best; } else if(i_best==best) ++cnt; } std::cout<<best<<" "<<cnt; return 0; } |