#include <bits/stdc++.h> #include <math.h> using namespace std; #define endl "\n" #define mp make_pair #define st first #define nd second #define pii pair<int, int> #define pb push_back #define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10), cin.tie(0), cout.tie(0); #define REP(i, n) for (int i = 0; i < (n); ++i) #define FWD(i, a, b) for (int i = (a); i < (b); ++i) #define rep(i, n) for (int i = 0; i < (n); ++i) #define fwd(i, a, b) for (int i = (a); i < (b); ++i) #define all(c) (c).begin(), (c).end() #define sz(X) (int)((X).size()) #define what(x) cerr << #x << " is " << x << endl; ostream &operator<<(ostream &out, string str) { for (char c : str) out << c; return out; } template <class L, class R> ostream &operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.st << ", " << p.nd << ")"; } template <class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) { out << '{'; for (auto it = a.begin(); it != a.end(); it = next(it)) out << (it != a.begin() ? ", " : "") << *it; return out << '}'; } void dump() { cerr << "\n"; } template <class T, class... Ts> void dump(T a, Ts... x) { cerr << a << ", "; dump(x...); } #define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__) #define int long long const int MAXN = 2500; char tab[MAXN][MAXN]; int M[MAXN][MAXN]; int n, m, k; void pre() { rep(i, MAXN) rep(j, MAXN) M[i][j] = -1, tab[i][j] = 'X'; } vector<pii> sasiedzi(pii A) { return {{A.st - 1, A.nd}, {A.st + 1, A.nd}, {A.st, A.nd + 1}, {A.st, A.nd - 1}}; } int bfs() { queue<pii> Q; Q.push({1, 1}); M[1][1] = 0; while (!Q.empty()) { pii q = Q.front(); if (q == make_pair(n, m)) return M[n][m]; Q.pop(); for (auto y : sasiedzi(q)) { if (tab[y.st][y.nd] != 'X' && M[y.st][y.nd] == -1) { M[y.st][y.nd] = M[q.st][q.nd] + 1; Q.push(y); } } } return -1111; } int32_t main() { _upgrade; pre(); cin >> n >> m >> k; rep(i, n) { string S; cin >> S; rep(j, m) tab[i + 1][j + 1] = S[j]; } int res = bfs(); int ileB = (res - n - m + 2) / 2; int ileA = res - ileB; debug(res, ileA, ileB); map<int, int> wyniki; rep(j, k) { int a, b; cin >> a >> b; wyniki[a * ileA + b * ileB]++; } // debug(wyniki); cout << wyniki.begin()->st << " " << wyniki.begin()->nd << endl; }
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 | #include <bits/stdc++.h> #include <math.h> using namespace std; #define endl "\n" #define mp make_pair #define st first #define nd second #define pii pair<int, int> #define pb push_back #define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10), cin.tie(0), cout.tie(0); #define REP(i, n) for (int i = 0; i < (n); ++i) #define FWD(i, a, b) for (int i = (a); i < (b); ++i) #define rep(i, n) for (int i = 0; i < (n); ++i) #define fwd(i, a, b) for (int i = (a); i < (b); ++i) #define all(c) (c).begin(), (c).end() #define sz(X) (int)((X).size()) #define what(x) cerr << #x << " is " << x << endl; ostream &operator<<(ostream &out, string str) { for (char c : str) out << c; return out; } template <class L, class R> ostream &operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.st << ", " << p.nd << ")"; } template <class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) { out << '{'; for (auto it = a.begin(); it != a.end(); it = next(it)) out << (it != a.begin() ? ", " : "") << *it; return out << '}'; } void dump() { cerr << "\n"; } template <class T, class... Ts> void dump(T a, Ts... x) { cerr << a << ", "; dump(x...); } #define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__) #define int long long const int MAXN = 2500; char tab[MAXN][MAXN]; int M[MAXN][MAXN]; int n, m, k; void pre() { rep(i, MAXN) rep(j, MAXN) M[i][j] = -1, tab[i][j] = 'X'; } vector<pii> sasiedzi(pii A) { return {{A.st - 1, A.nd}, {A.st + 1, A.nd}, {A.st, A.nd + 1}, {A.st, A.nd - 1}}; } int bfs() { queue<pii> Q; Q.push({1, 1}); M[1][1] = 0; while (!Q.empty()) { pii q = Q.front(); if (q == make_pair(n, m)) return M[n][m]; Q.pop(); for (auto y : sasiedzi(q)) { if (tab[y.st][y.nd] != 'X' && M[y.st][y.nd] == -1) { M[y.st][y.nd] = M[q.st][q.nd] + 1; Q.push(y); } } } return -1111; } int32_t main() { _upgrade; pre(); cin >> n >> m >> k; rep(i, n) { string S; cin >> S; rep(j, m) tab[i + 1][j + 1] = S[j]; } int res = bfs(); int ileB = (res - n - m + 2) / 2; int ileA = res - ileB; debug(res, ileA, ileB); map<int, int> wyniki; rep(j, k) { int a, b; cin >> a >> b; wyniki[a * ileA + b * ileB]++; } // debug(wyniki); cout << wyniki.begin()->st << " " << wyniki.begin()->nd << endl; } |