#include <iostream> #include <bitset> #include <vector> constexpr int LCM = 840; int main() { int n, m, q; std::cin >> n >> m >> q; std::vector<std::vector<std::bitset<LCM>>> desc(n, std::vector<std::bitset<LCM>>(m)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { std::string s; std::cin >> s; for (int t = 0; t < LCM; ++t) { desc[i][j][t] = s[t % s.size()] == '1'; } } } std::bitset<LCM> hor, ver; std::vector<std::vector<std::pair<int, int>>> bounds(LCM, std::vector<std::pair<int, int>>()); for (int t = 0; t < LCM; ++t) { // Hor int start_bound = 0; for (int i = 0; i < n; ++i) { bool full = true; for (int j = 0; full && j < m; ++j) { full &= desc[i][j][t]; } if (full) { if (!hor[t]) { hor[t] = true; bounds[t] = std::vector<std::pair<int, int>>(n + 1); } for (int i_ = start_bound; i_ <= i; ++i_) { bounds[t][i_] = { start_bound, i }; } start_bound = i + 1; } } if (hor[t]) { for (int i_ = start_bound; i_ <= n; ++i_) { bounds[t][i_] = { start_bound, n }; } } else { // Ver start_bound = 0; for (int j = 0; j < m; ++j) { bool full = true; for (int i = 0; full && i < n; ++i) { full &= !desc[i][j][t]; } if (full) { if (!ver[t]) { ver[t] = true; bounds[t] = std::vector<std::pair<int, int>>(m + 1); } for (int j_ = start_bound; j_ <= j; ++j_) { bounds[t][j_] = { start_bound, j }; } start_bound = j + 1; } } if (ver[t]) { for (int j_ = start_bound; j_ <= m; ++j_) { bounds[t][j_] = { start_bound, m }; } } } } // DEBUG /* for (int t = 0; t < LCM; ++t) { std::cerr << "t: " << t << "\n"; if (ver[t]) { std::cerr << "ver\n"; } else if (hor[t]) { std::cerr << "hor\n"; } else { std::cerr << "free\n"; continue; } for (int i = 0; i < (hor[t] ? n : m) + 1; ++i) { std::cerr << i << ": [" << bounds[t][i].first << ", " << bounds[t][i].second << "]\n"; } } */ for (int l = 0; l < q; ++l) { int t, a, b, c, d; std::cin >> t >> a >> b >> c >> d; int t0 = t % LCM; if (hor[t0]) { //std::cerr << "hor " << a << "->" << c << "\n"; std::pair<int, int> curr = { a, a }; for (int tp = 0; ; ++tp) { if (!hor[(t0 + tp) % LCM]) { //std::cerr << "cross\n"; std::cout << t + tp << "\n"; break; } curr.first = bounds[(t0 + tp) % LCM][curr.first].first; curr.second = bounds[(t0 + tp) % LCM][curr.second].second; //std::cerr << "t: " << t0 + tp << " [" << curr.first << ", " << curr.second << "]\n"; if (curr.first <= c && curr.second >= c) { std::cout << t + tp << "\n"; break; } } } else if (ver[t0]) { //std::cerr << "ver " << b << "->" << d << "\n"; std::pair<int, int> curr = { b, b }; for (int tp = 0; ; ++tp) { if (!ver[(t0 + tp) % LCM]) { //std::cerr << "cross\n"; std::cout << t + tp << "\n"; break; } curr.first = bounds[(t0 + tp) % LCM][curr.first].first; curr.second = bounds[(t0 + tp) % LCM][curr.second].second; //std::cerr << "t: " << t0 + tp << " [" << curr.first << ", " << curr.second << "]\n"; if (curr.first <= d && curr.second >= d) { std::cout << t + tp << "\n"; break; } } } else { std::cout << t << "\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 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 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 | #include <iostream> #include <bitset> #include <vector> constexpr int LCM = 840; int main() { int n, m, q; std::cin >> n >> m >> q; std::vector<std::vector<std::bitset<LCM>>> desc(n, std::vector<std::bitset<LCM>>(m)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { std::string s; std::cin >> s; for (int t = 0; t < LCM; ++t) { desc[i][j][t] = s[t % s.size()] == '1'; } } } std::bitset<LCM> hor, ver; std::vector<std::vector<std::pair<int, int>>> bounds(LCM, std::vector<std::pair<int, int>>()); for (int t = 0; t < LCM; ++t) { // Hor int start_bound = 0; for (int i = 0; i < n; ++i) { bool full = true; for (int j = 0; full && j < m; ++j) { full &= desc[i][j][t]; } if (full) { if (!hor[t]) { hor[t] = true; bounds[t] = std::vector<std::pair<int, int>>(n + 1); } for (int i_ = start_bound; i_ <= i; ++i_) { bounds[t][i_] = { start_bound, i }; } start_bound = i + 1; } } if (hor[t]) { for (int i_ = start_bound; i_ <= n; ++i_) { bounds[t][i_] = { start_bound, n }; } } else { // Ver start_bound = 0; for (int j = 0; j < m; ++j) { bool full = true; for (int i = 0; full && i < n; ++i) { full &= !desc[i][j][t]; } if (full) { if (!ver[t]) { ver[t] = true; bounds[t] = std::vector<std::pair<int, int>>(m + 1); } for (int j_ = start_bound; j_ <= j; ++j_) { bounds[t][j_] = { start_bound, j }; } start_bound = j + 1; } } if (ver[t]) { for (int j_ = start_bound; j_ <= m; ++j_) { bounds[t][j_] = { start_bound, m }; } } } } // DEBUG /* for (int t = 0; t < LCM; ++t) { std::cerr << "t: " << t << "\n"; if (ver[t]) { std::cerr << "ver\n"; } else if (hor[t]) { std::cerr << "hor\n"; } else { std::cerr << "free\n"; continue; } for (int i = 0; i < (hor[t] ? n : m) + 1; ++i) { std::cerr << i << ": [" << bounds[t][i].first << ", " << bounds[t][i].second << "]\n"; } } */ for (int l = 0; l < q; ++l) { int t, a, b, c, d; std::cin >> t >> a >> b >> c >> d; int t0 = t % LCM; if (hor[t0]) { //std::cerr << "hor " << a << "->" << c << "\n"; std::pair<int, int> curr = { a, a }; for (int tp = 0; ; ++tp) { if (!hor[(t0 + tp) % LCM]) { //std::cerr << "cross\n"; std::cout << t + tp << "\n"; break; } curr.first = bounds[(t0 + tp) % LCM][curr.first].first; curr.second = bounds[(t0 + tp) % LCM][curr.second].second; //std::cerr << "t: " << t0 + tp << " [" << curr.first << ", " << curr.second << "]\n"; if (curr.first <= c && curr.second >= c) { std::cout << t + tp << "\n"; break; } } } else if (ver[t0]) { //std::cerr << "ver " << b << "->" << d << "\n"; std::pair<int, int> curr = { b, b }; for (int tp = 0; ; ++tp) { if (!ver[(t0 + tp) % LCM]) { //std::cerr << "cross\n"; std::cout << t + tp << "\n"; break; } curr.first = bounds[(t0 + tp) % LCM][curr.first].first; curr.second = bounds[(t0 + tp) % LCM][curr.second].second; //std::cerr << "t: " << t0 + tp << " [" << curr.first << ", " << curr.second << "]\n"; if (curr.first <= d && curr.second >= d) { std::cout << t + tp << "\n"; break; } } } else { std::cout << t << "\n"; } } } |