#include <bits/stdc++.h> #include <iostream> #define CYCLE 840 using namespace std; int n, m, q; vector<string> s[15002]; set<int> blocks[842]; bool h[842], v[842]; int main () { cin >> n >> m >> q; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { string temp; cin >> temp; s[i].push_back(temp); } } for (int i = 1; i <= n; i++) { set<int> poss; set< pair<int, int> > typ; for (int j = 0; j < CYCLE ; j++) { poss.insert(j); } for (int j = 0; j < m; j++) { for (int k = 0; k < s[i][j].length(); k++) { if (s[i][j][k] == '0') { if (typ.find({k, s[i][j].length()}) == typ.end()) { typ.insert({k, s[i][j].length()}); for (int l = k; l < CYCLE ; l += s[i][j].length()) { poss.erase(l); } } } } if (poss.empty()) break; } if (!poss.empty()) { for (auto elem : poss) { h[elem] = true; blocks[elem].insert(i); } } } for (int i = 0; i < m; i++) { set<int> poss; set< pair<int, int> > typ; for (int j = 0; j < CYCLE ; j++) { poss.insert(j); } for (int j = 1; j <= n; j++) { for (int k = 0; k < s[j][i].length(); k++) { if (s[j][i][k] == '1') { if (typ.find({k, s[j][i].length()}) == typ.end()) { typ.insert({k, s[j][i].length()}); for (int l = k; l < CYCLE ; l += s[j][i].length()) { poss.erase(l); } } } } if (poss.empty()) break; } if (!poss.empty()) { for (auto elem : poss) { v[elem] = true; blocks[elem].insert(i + 1); } } } // DEBUG // for (int i = 0; i <= 17; i++) { // cout << "t: " << i << endl; // if (h[i]) { // cout << 'H' << endl; // } else if (v[i]) { // cout << 'V' << endl; // } // for (auto elem : blocks[i]) { // cout << elem << " "; // } // cout << "_________" << endl; // } for (int i = 0; i < CYCLE ; i++) { if ((!h[i]) && (!v[i])) { continue; } blocks[i].insert(0); blocks[i].insert(16000); } while (q--) { int tim, x1, y1, x2, y2; cin >> tim >> x1 >> y1 >> x2 >> y2; int tim_mod = tim % CYCLE; if ((!h[tim_mod]) && (!v[tim_mod])) { cout << tim << endl; continue; } if (v[tim_mod]) { x1 = y1; x2 = y2; } if (x1 == x2) { cout << tim << endl; continue; } bool type_comp = h[tim_mod]; int counter = tim; int pos = x1; while (1) { if ((type_comp && (!h[tim_mod])) || ((!type_comp) && (!v[tim_mod]))) { break; } if (x2 > pos) { int rang = *blocks[tim_mod].upper_bound(pos); if (rang > x2) { break; } pos = rang; } else { auto iter = blocks[tim_mod].upper_bound(pos); int rang = *(--iter); // cout << "RANG " << rang << endl; if (rang <= x2) { break; } pos = rang; } counter++; tim_mod = counter % CYCLE; } cout << counter << endl; } return 0; }
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 141 142 | #include <bits/stdc++.h> #include <iostream> #define CYCLE 840 using namespace std; int n, m, q; vector<string> s[15002]; set<int> blocks[842]; bool h[842], v[842]; int main () { cin >> n >> m >> q; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { string temp; cin >> temp; s[i].push_back(temp); } } for (int i = 1; i <= n; i++) { set<int> poss; set< pair<int, int> > typ; for (int j = 0; j < CYCLE ; j++) { poss.insert(j); } for (int j = 0; j < m; j++) { for (int k = 0; k < s[i][j].length(); k++) { if (s[i][j][k] == '0') { if (typ.find({k, s[i][j].length()}) == typ.end()) { typ.insert({k, s[i][j].length()}); for (int l = k; l < CYCLE ; l += s[i][j].length()) { poss.erase(l); } } } } if (poss.empty()) break; } if (!poss.empty()) { for (auto elem : poss) { h[elem] = true; blocks[elem].insert(i); } } } for (int i = 0; i < m; i++) { set<int> poss; set< pair<int, int> > typ; for (int j = 0; j < CYCLE ; j++) { poss.insert(j); } for (int j = 1; j <= n; j++) { for (int k = 0; k < s[j][i].length(); k++) { if (s[j][i][k] == '1') { if (typ.find({k, s[j][i].length()}) == typ.end()) { typ.insert({k, s[j][i].length()}); for (int l = k; l < CYCLE ; l += s[j][i].length()) { poss.erase(l); } } } } if (poss.empty()) break; } if (!poss.empty()) { for (auto elem : poss) { v[elem] = true; blocks[elem].insert(i + 1); } } } // DEBUG // for (int i = 0; i <= 17; i++) { // cout << "t: " << i << endl; // if (h[i]) { // cout << 'H' << endl; // } else if (v[i]) { // cout << 'V' << endl; // } // for (auto elem : blocks[i]) { // cout << elem << " "; // } // cout << "_________" << endl; // } for (int i = 0; i < CYCLE ; i++) { if ((!h[i]) && (!v[i])) { continue; } blocks[i].insert(0); blocks[i].insert(16000); } while (q--) { int tim, x1, y1, x2, y2; cin >> tim >> x1 >> y1 >> x2 >> y2; int tim_mod = tim % CYCLE; if ((!h[tim_mod]) && (!v[tim_mod])) { cout << tim << endl; continue; } if (v[tim_mod]) { x1 = y1; x2 = y2; } if (x1 == x2) { cout << tim << endl; continue; } bool type_comp = h[tim_mod]; int counter = tim; int pos = x1; while (1) { if ((type_comp && (!h[tim_mod])) || ((!type_comp) && (!v[tim_mod]))) { break; } if (x2 > pos) { int rang = *blocks[tim_mod].upper_bound(pos); if (rang > x2) { break; } pos = rang; } else { auto iter = blocks[tim_mod].upper_bound(pos); int rang = *(--iter); // cout << "RANG " << rang << endl; if (rang <= x2) { break; } pos = rang; } counter++; tim_mod = counter % CYCLE; } cout << counter << endl; } return 0; } |