#include <cstdio> #include <algorithm> #include <queue> #include <utility> using namespace std; #define MAX_MN 2000 + 10 #define MAX_Z 1000000 + 10 char mapa[MAX_MN][MAX_MN]; long long int znajomi[MAX_Z]; long long int odleglosci[MAX_MN][MAX_MN]; bool odwiedzone[MAX_MN][MAX_MN]; bool czy_bezpieczny(int x, int y, int n, int m) { if (x < 0 || y < 0) { return false; } if (x >= n || y >= m) { return false; } if (mapa[x][y] == 'X') { return false; } return true; } int main() { long long int n, m, k; scanf("%lld %lld %lld", &n, &m, &k); getc(stdin); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { mapa[i][j] = getc(stdin); } getc(stdin); } queue<pair<int, int>> kolejka; kolejka.push(make_pair(0, 0)); odwiedzone[0][0] = true; while(! kolejka.empty()) { pair<int, int> biezacy = kolejka.front(); kolejka.pop(); if (czy_bezpieczny(biezacy.first - 1, biezacy.second, n, m) && ! odwiedzone[biezacy.first - 1][biezacy.second]) { odwiedzone[biezacy.first - 1][biezacy.second] = true; odleglosci[biezacy.first - 1][biezacy.second] = odleglosci[biezacy.first][biezacy.second] + 1; kolejka.push(make_pair(biezacy.first - 1, biezacy.second)); } if (czy_bezpieczny(biezacy.first + 1, biezacy.second, n, m) && ! odwiedzone[biezacy.first + 1][biezacy.second]) { odwiedzone[biezacy.first + 1][biezacy.second] = true; odleglosci[biezacy.first + 1][biezacy.second] = odleglosci[biezacy.first][biezacy.second] + 1; kolejka.push(make_pair(biezacy.first + 1, biezacy.second)); } if (czy_bezpieczny(biezacy.first, biezacy.second - 1, n, m) && ! odwiedzone[biezacy.first][biezacy.second - 1]) { odwiedzone[biezacy.first][biezacy.second - 1] = true; odleglosci[biezacy.first][biezacy.second - 1] = odleglosci[biezacy.first][biezacy.second] + 1; kolejka.push(make_pair(biezacy.first, biezacy.second - 1)); } if (czy_bezpieczny(biezacy.first, biezacy.second + 1, n, m) && ! odwiedzone[biezacy.first][biezacy.second + 1]) { odwiedzone[biezacy.first][biezacy.second + 1] = true; odleglosci[biezacy.first][biezacy.second + 1] = odleglosci[biezacy.first][biezacy.second] + 1; kolejka.push(make_pair(biezacy.first, biezacy.second + 1)); } } long long int liczba_cofniec = (odleglosci[n - 1][m - 1] - (n + m - 2)) / 2; long long int a, b; for (int i = 0; i < k; i++) { scanf("%lld %lld", &a, &b); znajomi[i] = a * (n + m - 2) + liczba_cofniec * (a + b); } sort(znajomi, znajomi + k); int ile = 0; for (int i = 0; i < k; i++) { if (znajomi[i] == znajomi[0]) { ile++; } else { break; } } printf("%lld %d", znajomi[0], 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 89 90 91 92 93 94 95 96 97 98 99 100 101 | #include <cstdio> #include <algorithm> #include <queue> #include <utility> using namespace std; #define MAX_MN 2000 + 10 #define MAX_Z 1000000 + 10 char mapa[MAX_MN][MAX_MN]; long long int znajomi[MAX_Z]; long long int odleglosci[MAX_MN][MAX_MN]; bool odwiedzone[MAX_MN][MAX_MN]; bool czy_bezpieczny(int x, int y, int n, int m) { if (x < 0 || y < 0) { return false; } if (x >= n || y >= m) { return false; } if (mapa[x][y] == 'X') { return false; } return true; } int main() { long long int n, m, k; scanf("%lld %lld %lld", &n, &m, &k); getc(stdin); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { mapa[i][j] = getc(stdin); } getc(stdin); } queue<pair<int, int>> kolejka; kolejka.push(make_pair(0, 0)); odwiedzone[0][0] = true; while(! kolejka.empty()) { pair<int, int> biezacy = kolejka.front(); kolejka.pop(); if (czy_bezpieczny(biezacy.first - 1, biezacy.second, n, m) && ! odwiedzone[biezacy.first - 1][biezacy.second]) { odwiedzone[biezacy.first - 1][biezacy.second] = true; odleglosci[biezacy.first - 1][biezacy.second] = odleglosci[biezacy.first][biezacy.second] + 1; kolejka.push(make_pair(biezacy.first - 1, biezacy.second)); } if (czy_bezpieczny(biezacy.first + 1, biezacy.second, n, m) && ! odwiedzone[biezacy.first + 1][biezacy.second]) { odwiedzone[biezacy.first + 1][biezacy.second] = true; odleglosci[biezacy.first + 1][biezacy.second] = odleglosci[biezacy.first][biezacy.second] + 1; kolejka.push(make_pair(biezacy.first + 1, biezacy.second)); } if (czy_bezpieczny(biezacy.first, biezacy.second - 1, n, m) && ! odwiedzone[biezacy.first][biezacy.second - 1]) { odwiedzone[biezacy.first][biezacy.second - 1] = true; odleglosci[biezacy.first][biezacy.second - 1] = odleglosci[biezacy.first][biezacy.second] + 1; kolejka.push(make_pair(biezacy.first, biezacy.second - 1)); } if (czy_bezpieczny(biezacy.first, biezacy.second + 1, n, m) && ! odwiedzone[biezacy.first][biezacy.second + 1]) { odwiedzone[biezacy.first][biezacy.second + 1] = true; odleglosci[biezacy.first][biezacy.second + 1] = odleglosci[biezacy.first][biezacy.second] + 1; kolejka.push(make_pair(biezacy.first, biezacy.second + 1)); } } long long int liczba_cofniec = (odleglosci[n - 1][m - 1] - (n + m - 2)) / 2; long long int a, b; for (int i = 0; i < k; i++) { scanf("%lld %lld", &a, &b); znajomi[i] = a * (n + m - 2) + liczba_cofniec * (a + b); } sort(znajomi, znajomi + k); int ile = 0; for (int i = 0; i < k; i++) { if (znajomi[i] == znajomi[0]) { ile++; } else { break; } } printf("%lld %d", znajomi[0], ile); return 0; } |