#include <bits/stdc++.h> #define int long long #define pb push_back #define st first #define nd second #define pii pair<int,int> #define mp make_pair #define pll pair<long long,long long> using namespace std; const int nax = 2005; char a[nax][nax]; int n,m,k; bool vis[nax][nax]; int odl[nax][nax]; bool ok(int r,int c) { if(r < 1 || c < 1 || r > n || c > m) return false; if(vis[r][c]) return false; if(a[r][c] == 'X') return false; return true; } vector<int> dx = {-1,1,0,0}; vector<int> dy = {0,0,-1,1}; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>m>>k; for(int i=1;i<=n;i++) { string s; cin>>s; for(int j=1;j<=m;j++) { a[i][j] = s[j - 1]; } } vis[1][1] = true; vector<pii> q; int wsk = 0; q.pb(mp(1,1)); vis[1][1] = true; while(wsk < q.size()) { pii cur = q[wsk]; wsk++; for(int i=0;i<4;i++) { int x = cur.st + dx[i]; int y = cur.nd + dy[i]; if(ok(x,y)) { odl[x][y] = odl[cur.st][cur.nd] + 1; vis[x][y] = true; q.pb(mp(x,y)); } } } int od = odl[n][m]; int ans = 4e18 + 5; int cnt = 0; while(k--) { int a,b; cin>>a>>b; int ctt = n - 1 + m - 1; int cur = (od - ctt) / 2; int wa = cur * (a + b); wa += ctt * a; if(wa < ans) { ans = wa; cnt = 1; } else if(wa == ans) { cnt++; } } cout<<ans<<" "<<cnt<<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 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 98 99 100 101 102 | #include <bits/stdc++.h> #define int long long #define pb push_back #define st first #define nd second #define pii pair<int,int> #define mp make_pair #define pll pair<long long,long long> using namespace std; const int nax = 2005; char a[nax][nax]; int n,m,k; bool vis[nax][nax]; int odl[nax][nax]; bool ok(int r,int c) { if(r < 1 || c < 1 || r > n || c > m) return false; if(vis[r][c]) return false; if(a[r][c] == 'X') return false; return true; } vector<int> dx = {-1,1,0,0}; vector<int> dy = {0,0,-1,1}; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>m>>k; for(int i=1;i<=n;i++) { string s; cin>>s; for(int j=1;j<=m;j++) { a[i][j] = s[j - 1]; } } vis[1][1] = true; vector<pii> q; int wsk = 0; q.pb(mp(1,1)); vis[1][1] = true; while(wsk < q.size()) { pii cur = q[wsk]; wsk++; for(int i=0;i<4;i++) { int x = cur.st + dx[i]; int y = cur.nd + dy[i]; if(ok(x,y)) { odl[x][y] = odl[cur.st][cur.nd] + 1; vis[x][y] = true; q.pb(mp(x,y)); } } } int od = odl[n][m]; int ans = 4e18 + 5; int cnt = 0; while(k--) { int a,b; cin>>a>>b; int ctt = n - 1 + m - 1; int cur = (od - ctt) / 2; int wa = cur * (a + b); wa += ctt * a; if(wa < ans) { ans = wa; cnt = 1; } else if(wa == ans) { cnt++; } } cout<<ans<<" "<<cnt<<endl; return 0; } |