1 条题解
-
0

#include <bits/stdc++.h> using std::cin; using std::cout; const int N = 1024; typedef std::pair <int, int> pr; typedef std::bitset <N> bitset; const pr failed = pr(INT_MIN, INT_MIN); inline int min(const int x, const int y) {return x < y ? x : y;} inline void up(int &x, const int y) {x < y ? x = y : 0;} inline void down(int &x, const int y) {x > y ? x = y : 0;} struct graph { bitset g[N]; int ar, ac, rightmost; friend std::istream & operator >> (std::istream &in, graph &B) { int i, j, r, c, min = N; bool ok = false; static char s[N]; in >> r >> c, B.rightmost = B.ar = B.ac = 0; for (i = 0; i < N; ++i) B.g[i].reset(); for (i = 0; r; --r, ++i) if (in >> s, ok || std::count(s, s + c, '*')) { for (j = 0; j < c; ++j) if (!(s[j] & 4)) B.g[i].set(j), up(B.rightmost, j); down(min, B.g[i]._Find_first()), ok = true; } else --i, ++B.ar; if (ok) for (B.ac = min, i = 0; i < N; ++i) B.g[i] >>= min; return in; } inline int significant() const {return g->_Find_first();} inline bool empty() const {return g->none();} } G1, G2, G3, G; bitset R[N]; pr check(const graph &G1, const graph &G2, const graph &goal) { int i, j, d, c1 = G1.significant(), c2 = G2.significant(); pr ret; if (c1 <= c2) { if (d = c2 - c1, G1.rightmost + d >= N) return failed; memcpy(R, G2.g, sizeof R); for (i = 0; i < N; ++i) R[i] ^= G1.g[i] << d; } else { if (d = c1 - c2, G2.rightmost + d >= N) return failed; memcpy(R, G1.g, sizeof R); for (i = 0; i < N; ++i) R[i] ^= G2.g[i] << d; d = 0; } for (i = 0; i < N && R[i].none(); ++i); if (i == N) return goal.empty() ? pr(0, 0) : failed; ret = pr(i, R[i]._Find_first() - goal.significant()); if (ret.second < 0) return failed; for (j = 0; i < N; ++i, ++j) { if ((int)R[i]._Find_first() < ret.second) return failed; if (R[i] >> ret.second != goal.g[j]) return failed; } for (; j < N; ++j) if (goal.g[j].any()) return failed; return ret.second -= d, ret; } int main() { int offset_r, offset_c; pr r; std::ios::sync_with_stdio(false), cin.tie(NULL); cin >> G1 >> G2 >> G3, offset_r = G1.ar - G2.ar, offset_c = G1.ac - G2.ac, r = check(G1, G2, G3); if (r != failed) return cout << "YES\n" << G1.significant() - G2.significant() + offset_c << ' ' << offset_r << '\n', 0; if (!G3.empty()) { r = check(G1, G3, G2); if (r != failed) return cout << "YES\n" << r.second + offset_c << ' ' << r.first + offset_r << '\n', 0; r = check(G2, G3, G1); if (r != failed) return cout << "YES\n" << -r.second + offset_c << ' ' << -r.first + offset_r << '\n', 0; } return cout << "NO\n", 0; }
- 1
信息
- ID
- 6516
- 时间
- 2000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者