#include <bits/stdc++.h> using namespace std; using pole = pair<int, int>; const int nax = 2e3 + 5; bool av[nax][nax], vis[nax][nax]; int dist[nax][nax]; vector<pole> moves = {{0, -1}, {-1, 0}, {1, 0}, {0, 1}}; bool ok(pole p) { return av[p.first][p.second]; } pole operator+(const pole &lhs, const pole &rhs) { return pole(lhs.first + rhs.first, lhs.second + rhs.second); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m, k; cin >> n >> m >> k; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { char c; cin >> c; av[i][j] = c == '.'; } } queue<pole> q; vis[1][1] = true; q.push({1, 1}); pole peak = pole{n, m}; while (not q.empty()) { auto v = q.front(); q.pop(); if (v == peak) { break; } for (auto p : moves) { auto u = v + p; if (vis[u.first][u.second] or not ok(u)) { continue; } dist[u.first][u.second] = dist[v.first][v.second] + 1; vis[u.first][u.second] = true; q.push(u); } } int extra_moves = dist[n][m] - (n - 1 + m - 1); map<long long, int> cnt; for (int i = 0; i < k; ++i) { int a, b; cin >> a >> b; cnt[(long long) a * (n - 1 + m - 1 + extra_moves / 2) + (long long) b * extra_moves / 2]++; } auto it = cnt.begin(); cout << it->first << " " << it->second << "\n"; }
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 | #include <bits/stdc++.h> using namespace std; using pole = pair<int, int>; const int nax = 2e3 + 5; bool av[nax][nax], vis[nax][nax]; int dist[nax][nax]; vector<pole> moves = {{0, -1}, {-1, 0}, {1, 0}, {0, 1}}; bool ok(pole p) { return av[p.first][p.second]; } pole operator+(const pole &lhs, const pole &rhs) { return pole(lhs.first + rhs.first, lhs.second + rhs.second); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m, k; cin >> n >> m >> k; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { char c; cin >> c; av[i][j] = c == '.'; } } queue<pole> q; vis[1][1] = true; q.push({1, 1}); pole peak = pole{n, m}; while (not q.empty()) { auto v = q.front(); q.pop(); if (v == peak) { break; } for (auto p : moves) { auto u = v + p; if (vis[u.first][u.second] or not ok(u)) { continue; } dist[u.first][u.second] = dist[v.first][v.second] + 1; vis[u.first][u.second] = true; q.push(u); } } int extra_moves = dist[n][m] - (n - 1 + m - 1); map<long long, int> cnt; for (int i = 0; i < k; ++i) { int a, b; cin >> a >> b; cnt[(long long) a * (n - 1 + m - 1 + extra_moves / 2) + (long long) b * extra_moves / 2]++; } auto it = cnt.begin(); cout << it->first << " " << it->second << "\n"; } |