#include <bits/stdc++.h> using namespace std; int n,m,k; char c[2001][2001]; vector <int> graf[4000001]; bool visited[4000001]; int d[4000001]; void bfs (int src) { queue <int> q; q.push(src); visited[src]=true; while (!q.empty()) { int v=q.front(); q.pop(); for(int i=0; i<graf[v].size(); i++) { if(!visited[graf[v][i]]) { visited[graf[v][i]]=true; d[graf[v][i]]=d[v]+1; q.push(graf[v][i]); } } } } int main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>> n>> m>> k; for (int i=0; i<n; i++) for (int j=0; j<m; j++) cin>> c[i][j]; for (int i=0; i<n; i++) for (int j=0; j<m-1; j++) if (c[i][j]=='.' && c[i][j+1]=='.') { graf[i*m+j].push_back(i*m+j+1); graf[i*m+j+1].push_back(i*m+j); } for (int i=0; i<n-1; i++) for (int j=0; j<m; j++) if (c[i+1][j]=='.' && c[i][j]=='.') { graf[i*m+j].push_back((i+1)*m+j); graf[(i+1)*m+j].push_back(i*m+j); } /*for (int i=0; i<n*m; i++) { cout<< i<< ": "; for (int j=0; j<graf[i].size(); j++) cout<< graf[i][j]<< ' '; cout<< '\n'; }*/ bfs(0); long long len=(long long)(d[n*m-1]); int ile=0; long long res=1000000000000000000; for (int i=0; i<k; i++) { long long a,b; cin>> a>> b; if ((n+m-2)*a+(len-(n+m-2))*(a+b)/2<res) { res=(n+m-2)*a+(len-(n+m-2))*(a+b)/2; ile=1; } else if ((n+m-2)*a+(len-(n+m-2))*(a+b)/2==res) ile++; } cout<< res<< ' '<< ile; 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 | #include <bits/stdc++.h> using namespace std; int n,m,k; char c[2001][2001]; vector <int> graf[4000001]; bool visited[4000001]; int d[4000001]; void bfs (int src) { queue <int> q; q.push(src); visited[src]=true; while (!q.empty()) { int v=q.front(); q.pop(); for(int i=0; i<graf[v].size(); i++) { if(!visited[graf[v][i]]) { visited[graf[v][i]]=true; d[graf[v][i]]=d[v]+1; q.push(graf[v][i]); } } } } int main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>> n>> m>> k; for (int i=0; i<n; i++) for (int j=0; j<m; j++) cin>> c[i][j]; for (int i=0; i<n; i++) for (int j=0; j<m-1; j++) if (c[i][j]=='.' && c[i][j+1]=='.') { graf[i*m+j].push_back(i*m+j+1); graf[i*m+j+1].push_back(i*m+j); } for (int i=0; i<n-1; i++) for (int j=0; j<m; j++) if (c[i+1][j]=='.' && c[i][j]=='.') { graf[i*m+j].push_back((i+1)*m+j); graf[(i+1)*m+j].push_back(i*m+j); } /*for (int i=0; i<n*m; i++) { cout<< i<< ": "; for (int j=0; j<graf[i].size(); j++) cout<< graf[i][j]<< ' '; cout<< '\n'; }*/ bfs(0); long long len=(long long)(d[n*m-1]); int ile=0; long long res=1000000000000000000; for (int i=0; i<k; i++) { long long a,b; cin>> a>> b; if ((n+m-2)*a+(len-(n+m-2))*(a+b)/2<res) { res=(n+m-2)*a+(len-(n+m-2))*(a+b)/2; ile=1; } else if ((n+m-2)*a+(len-(n+m-2))*(a+b)/2==res) ile++; } cout<< res<< ' '<< ile; return 0; } |