#include <bits/stdc++.h> using namespace std; long long n,m,k; long long a,b,w,wynik1,wynik2; long long t[2002][2002]; long long o[2002][2002]; queue < pair< pair<long long,long long> , long long > > q; char x; void bfs(long long w1, long long w2) { q.push({{w1,w2},1}); o[n][m]=1; while (!q.empty()) { w1=q.front().first.first; w2=q.front().first.second; //cout << w1 << " " << w2 << " " << q.front().second << endl; if (q.front().second == o[w1][w2]) { if (t[w1-1][w2] && o[w1-1][w2] == 0) { o[w1-1][w2]=o[w1][w2]; q.push({{w1-1,w2},o[w1-1][w2]}); } if (t[w1+1][w2] && o[w1+1][w2] == 0) { o[w1+1][w2]=o[w1][w2]+1; q.push({{w1+1,w2},o[w1+1][w2]}); } if (t[w1][w2-1] && o[w1][w2-1] == 0) { o[w1][w2-1]=o[w1][w2]; q.push({{w1,w2-1},o[w1][w2-1]}); } if (t[w1][w2+1] && o[w1][w2+1] == 0) { o[w1][w2+1]=o[w1][w2]+1; q.push({{w1,w2+1},o[w1][w2+1]}); } } q.pop(); } } int main() { scanf("%lld%lld%lld",&n,&m,&k); for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) { scanf(" %c",&x); if (x=='.') t[i][j]=1; } } bfs(n,m); o[1][1]--; //cout << endl << endl << o[1][1] << endl << endl; wynik1 = 213721372137213769; for (int i=1; i<=k; i++) { scanf("%lld%lld",&a,&b); w=(n+m-2+o[1][1])*a+o[1][1]*b; if (w < wynik1) { wynik1=w; wynik2=1; } else if (w == wynik1) wynik2++; } printf("%lld %lld\n",wynik1,wynik2); }
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 | #include <bits/stdc++.h> using namespace std; long long n,m,k; long long a,b,w,wynik1,wynik2; long long t[2002][2002]; long long o[2002][2002]; queue < pair< pair<long long,long long> , long long > > q; char x; void bfs(long long w1, long long w2) { q.push({{w1,w2},1}); o[n][m]=1; while (!q.empty()) { w1=q.front().first.first; w2=q.front().first.second; //cout << w1 << " " << w2 << " " << q.front().second << endl; if (q.front().second == o[w1][w2]) { if (t[w1-1][w2] && o[w1-1][w2] == 0) { o[w1-1][w2]=o[w1][w2]; q.push({{w1-1,w2},o[w1-1][w2]}); } if (t[w1+1][w2] && o[w1+1][w2] == 0) { o[w1+1][w2]=o[w1][w2]+1; q.push({{w1+1,w2},o[w1+1][w2]}); } if (t[w1][w2-1] && o[w1][w2-1] == 0) { o[w1][w2-1]=o[w1][w2]; q.push({{w1,w2-1},o[w1][w2-1]}); } if (t[w1][w2+1] && o[w1][w2+1] == 0) { o[w1][w2+1]=o[w1][w2]+1; q.push({{w1,w2+1},o[w1][w2+1]}); } } q.pop(); } } int main() { scanf("%lld%lld%lld",&n,&m,&k); for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) { scanf(" %c",&x); if (x=='.') t[i][j]=1; } } bfs(n,m); o[1][1]--; //cout << endl << endl << o[1][1] << endl << endl; wynik1 = 213721372137213769; for (int i=1; i<=k; i++) { scanf("%lld%lld",&a,&b); w=(n+m-2+o[1][1])*a+o[1][1]*b; if (w < wynik1) { wynik1=w; wynik2=1; } else if (w == wynik1) wynik2++; } printf("%lld %lld\n",wynik1,wynik2); } |