#include<cstdio> #include<iostream> #include<queue> using namespace std; int n, m, k; char znak; long long int a, b, x, y; int odw[2005][2005]; int odl[2005][2005]; int ok[2005][2005]; queue<pair<int, int> > kolejka; pair<int, int> poz; int leaders; long long int czas, minn; void go() { while(!kolejka.empty()) { poz = kolejka.front(); kolejka.pop(); x = poz.first; y = poz.second; if(odw[x][y] == 0) { odw[x][y] = 1; if(x-1 >= 1 && ok[x-1][y] == 1) { kolejka.push(make_pair(x-1, y)); odl[x-1][y] = min(odl[x-1][y], odl[x][y] + 1); } if(y-1 >= 1 && ok[x][y-1] == 1) { kolejka.push(make_pair(x, y-1)); odl[x][y-1] = min(odl[x][y-1], odl[x][y] + 1); } if(x+1 <= n && ok[x+1][y] == 1) { kolejka.push(make_pair(x+1, y)); odl[x+1][y] = min(odl[x+1][y], odl[x][y]); } if(y+1 <= m && ok[x][y+1] == 1) { kolejka.push(make_pair(x, y+1)); odl[x][y+1] = min(odl[x][y+1], odl[x][y]); } } } } int main() { ios_base::sync_with_stdio(0); cin >> n >> m >> k; for(int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> znak; if(znak == '.') { ok[i][j] = 1;} else { ok[i][j] = 0;} odl[i][j] = n*m; } } odl[1][1] = 0; kolejka.push(make_pair(1,1)); go(); minn = -1; for (int i = 1; i <= k; i++) { cin >> a >> b; czas = a*(n+m-2) + (a+b)*odl[n][m]; if(czas < minn || minn == -1) { minn = czas; leaders = 1; } else if(czas == minn) { leaders++; } } cout << minn << " " << leaders; 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 | #include<cstdio> #include<iostream> #include<queue> using namespace std; int n, m, k; char znak; long long int a, b, x, y; int odw[2005][2005]; int odl[2005][2005]; int ok[2005][2005]; queue<pair<int, int> > kolejka; pair<int, int> poz; int leaders; long long int czas, minn; void go() { while(!kolejka.empty()) { poz = kolejka.front(); kolejka.pop(); x = poz.first; y = poz.second; if(odw[x][y] == 0) { odw[x][y] = 1; if(x-1 >= 1 && ok[x-1][y] == 1) { kolejka.push(make_pair(x-1, y)); odl[x-1][y] = min(odl[x-1][y], odl[x][y] + 1); } if(y-1 >= 1 && ok[x][y-1] == 1) { kolejka.push(make_pair(x, y-1)); odl[x][y-1] = min(odl[x][y-1], odl[x][y] + 1); } if(x+1 <= n && ok[x+1][y] == 1) { kolejka.push(make_pair(x+1, y)); odl[x+1][y] = min(odl[x+1][y], odl[x][y]); } if(y+1 <= m && ok[x][y+1] == 1) { kolejka.push(make_pair(x, y+1)); odl[x][y+1] = min(odl[x][y+1], odl[x][y]); } } } } int main() { ios_base::sync_with_stdio(0); cin >> n >> m >> k; for(int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> znak; if(znak == '.') { ok[i][j] = 1;} else { ok[i][j] = 0;} odl[i][j] = n*m; } } odl[1][1] = 0; kolejka.push(make_pair(1,1)); go(); minn = -1; for (int i = 1; i <= k; i++) { cin >> a >> b; czas = a*(n+m-2) + (a+b)*odl[n][m]; if(czas < minn || minn == -1) { minn = czas; leaders = 1; } else if(czas == minn) { leaders++; } } cout << minn << " " << leaders; return 0; } |