#include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int,int> PII; typedef double db; //mt19937 mrand(random_device{}()); const ll mod=1000000007; //int rnd(int x) { return mrand() % x;} ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} int gcd(int a,int b) { return b?gcd(b,a%b):a;} // head const int N=2e3+5; #define INF 0x3f3f3f3f template<class T> inline void read(T &x) { x=0; int c=getchar(),f=1; for (;!isdigit(c);c=getchar()) if (c==45) f=-1; for (;isdigit(c);c=getchar()) (x*=10)+=f*(c-'0'); } int n,m,k,dis[N][N]; PII cnt[N][N]; char s[N][N]; void dijkstra() { rep(i,0,n) fill(dis[i],dis[i]+m,INF); priority_queue<pair<int,PII>,vector<pair<int,PII>>,greater<pair<int,PII>>> pq; dis[0][0]=0; pq.push(mp(0,mp(0,0))); while (!pq.empty()) { int i=pq.top().se.fi,j=pq.top().se.se; pq.pop(); if (i<n-1&&s[i+1][j]!='X'&&dis[i+1][j]>dis[i][j]+1) { dis[i+1][j]=dis[i][j]+1; pq.push(mp(dis[i+1][j],mp(i+1,j))); cnt[i+1][j]=mp(cnt[i][j].fi+1,cnt[i][j].se); } if (j<m-1&&s[i][j+1]!='X'&&dis[i][j+1]>dis[i][j]+1){ dis[i][j+1]=dis[i][j]+1; pq.push(mp(dis[i][j+1],mp(i,j+1))); cnt[i][j+1]=mp(cnt[i][j].fi+1,cnt[i][j].se); } if (i>0&&s[i-1][j]!='X'&&dis[i-1][j]>dis[i][j]+2) { dis[i-1][j]=dis[i][j]+2; pq.push(mp(dis[i-1][j],mp(i-1,j))); cnt[i-1][j]=mp(cnt[i][j].fi,cnt[i][j].se+1); } if (j>0&&s[i][j-1]!='X'&&dis[i][j-1]>dis[i][j]+2) { dis[i][j-1]=dis[i][j]+2; pq.push(mp(dis[i][j-1],mp(i,j-1))); cnt[i][j-1]=mp(cnt[i][j].fi,cnt[i][j].se+1); } } } int main() { read(n); read(m); read(k); rep(i,0,n) scanf("%s",s[i]); dijkstra(); ll ans=numeric_limits<ll>::max(); int ctr=0; rep(i,0,k) { int a,b; read(a); read(b); ll cand=1ll*a*cnt[n-1][m-1].fi+1ll*b*cnt[n-1][m-1].se; if (ans==cand) ctr++; else if (ans>cand) ans=cand,ctr=1; } printf("%lld %d\n",ans,ctr); }
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; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int,int> PII; typedef double db; //mt19937 mrand(random_device{}()); const ll mod=1000000007; //int rnd(int x) { return mrand() % x;} ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} int gcd(int a,int b) { return b?gcd(b,a%b):a;} // head const int N=2e3+5; #define INF 0x3f3f3f3f template<class T> inline void read(T &x) { x=0; int c=getchar(),f=1; for (;!isdigit(c);c=getchar()) if (c==45) f=-1; for (;isdigit(c);c=getchar()) (x*=10)+=f*(c-'0'); } int n,m,k,dis[N][N]; PII cnt[N][N]; char s[N][N]; void dijkstra() { rep(i,0,n) fill(dis[i],dis[i]+m,INF); priority_queue<pair<int,PII>,vector<pair<int,PII>>,greater<pair<int,PII>>> pq; dis[0][0]=0; pq.push(mp(0,mp(0,0))); while (!pq.empty()) { int i=pq.top().se.fi,j=pq.top().se.se; pq.pop(); if (i<n-1&&s[i+1][j]!='X'&&dis[i+1][j]>dis[i][j]+1) { dis[i+1][j]=dis[i][j]+1; pq.push(mp(dis[i+1][j],mp(i+1,j))); cnt[i+1][j]=mp(cnt[i][j].fi+1,cnt[i][j].se); } if (j<m-1&&s[i][j+1]!='X'&&dis[i][j+1]>dis[i][j]+1){ dis[i][j+1]=dis[i][j]+1; pq.push(mp(dis[i][j+1],mp(i,j+1))); cnt[i][j+1]=mp(cnt[i][j].fi+1,cnt[i][j].se); } if (i>0&&s[i-1][j]!='X'&&dis[i-1][j]>dis[i][j]+2) { dis[i-1][j]=dis[i][j]+2; pq.push(mp(dis[i-1][j],mp(i-1,j))); cnt[i-1][j]=mp(cnt[i][j].fi,cnt[i][j].se+1); } if (j>0&&s[i][j-1]!='X'&&dis[i][j-1]>dis[i][j]+2) { dis[i][j-1]=dis[i][j]+2; pq.push(mp(dis[i][j-1],mp(i,j-1))); cnt[i][j-1]=mp(cnt[i][j].fi,cnt[i][j].se+1); } } } int main() { read(n); read(m); read(k); rep(i,0,n) scanf("%s",s[i]); dijkstra(); ll ans=numeric_limits<ll>::max(); int ctr=0; rep(i,0,k) { int a,b; read(a); read(b); ll cand=1ll*a*cnt[n-1][m-1].fi+1ll*b*cnt[n-1][m-1].se; if (ans==cand) ctr++; else if (ans>cand) ans=cand,ctr=1; } printf("%lld %d\n",ans,ctr); } |