#include <cstdio> #include <vector> #include <string> #include <algorithm> #include <cstring> using namespace std; const int M = 15013; const int Q = 840; vector<int> rzad(int x[9][9]) { vector<int> c(Q); for (int d = 2; d <= 8; d++) for(int i = 0; i < d; i++) if(x[d][i]) { for (int e = i; e < Q; e += d) c[e] = 1; } return c; } int go(vector<int> r, int t) { while(!r[t % Q]) t++; return t; } int solve(vector<int> r[M], int from, int to, int t) { while (from < to) { t = go(r[from+1], t); from++; } while (from > to) { t = go(r[from], t); from--; } return t; } int r[M][9][9], k[M][9][9]; vector<int> rr[M], kk[M]; int main() { int n,m,q; char ss[13]; scanf("%d %d %d", &n,&m,&q); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { scanf("%s", ss); int d = strlen(ss); for (int x = 0; x < d; x++) if(ss[x] == '0') r[i][d][x] = 1; else k[j][d][x] = 1; } for (int i = 1; i <= n; i++) { rr[i] = rzad(r[i]); } for (int i = 1; i <= m; i++) { kk[i] = rzad(k[i]); } for (int i = 0; i < q; i++) { int t,a,b,c,d; scanf("%d %d %d %d %d",&t,&a,&b,&c,&d); int ret = std::max(solve(rr, a, c, t), solve(kk, b, d, t)); printf("%d\n", ret); } 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 | #include <cstdio> #include <vector> #include <string> #include <algorithm> #include <cstring> using namespace std; const int M = 15013; const int Q = 840; vector<int> rzad(int x[9][9]) { vector<int> c(Q); for (int d = 2; d <= 8; d++) for(int i = 0; i < d; i++) if(x[d][i]) { for (int e = i; e < Q; e += d) c[e] = 1; } return c; } int go(vector<int> r, int t) { while(!r[t % Q]) t++; return t; } int solve(vector<int> r[M], int from, int to, int t) { while (from < to) { t = go(r[from+1], t); from++; } while (from > to) { t = go(r[from], t); from--; } return t; } int r[M][9][9], k[M][9][9]; vector<int> rr[M], kk[M]; int main() { int n,m,q; char ss[13]; scanf("%d %d %d", &n,&m,&q); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { scanf("%s", ss); int d = strlen(ss); for (int x = 0; x < d; x++) if(ss[x] == '0') r[i][d][x] = 1; else k[j][d][x] = 1; } for (int i = 1; i <= n; i++) { rr[i] = rzad(r[i]); } for (int i = 1; i <= m; i++) { kk[i] = rzad(k[i]); } for (int i = 0; i < q; i++) { int t,a,b,c,d; scanf("%d %d %d %d %d",&t,&a,&b,&c,&d); int ret = std::max(solve(rr, a, c, t), solve(kk, b, d, t)); printf("%d\n", ret); } return 0; } |