#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"; } |
English