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
|
using namespace std;
const int MAX = 1005;
const int INF = 0x3f3f3f3f;
int data[MAX][MAX], dp[MAX][MAX], csum[MAX][MAX], rsum[MAX][MAX];
int n, m;
void () {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (data[i][j]) {
rsum[i][j] += rsum[i - 1][j] + 1;
csum[i][j] += csum[i][j - 1] + 1;
} else {
rsum[i][j] = csum[i][j] = 0;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = data[i][j] ? 1 : 0;
if (dp[i - 1][j - 1]) {
int v = dp[i - 1][j - 1];
int c = csum[i][j];
int r = rsum[i][j];
dp[i][j] = min(v + 1, min(r, c));
}
}
}
}
int low_log[MAX];
void init() {
int cnt = 0, now = 1;
for (int i = 1; i < MAX; i++) {
if (now * 2 <= i) cnt++, now *= 2;
low_log[i] = cnt;
}
}
int ans[MAX][MAX][10][10];
void cal() {
for (int x = 0; x < 10; x++) {
for (int y = 0; y < 10; y++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (x + y == 0) {
ans[i][j][0][0] = dp[i][j];
continue;
}
int dx = x > 0 ? (1 << (x - 1)) : 0;
int dy = y > 0 ? (1 << (y - 1)) : 0;
int ox = max(0, x - 1);
int oy = max(0, y - 1);
int A = ans[i][j][ox][oy];
int B = i + dx > n ? 0 : ans[i + dx][j][ox][oy];
int C = j + dy > m ? 0 : ans[i][j + dy][ox][oy];
int D = (i + dx > n || j + dy > m) ? 0 : ans[i + dx][j + dy][ox][oy];
ans[i][j][x][y] = max(max(A, B), max(C, D));
}
}
}
}
}
int query(int x1, int y1, int x2, int y2) {
int px = low_log[x2 - x1 + 1];
int py = low_log[y2 - y1 + 1];
int dx = (1 << px) - 1;
int dy = (1 << py) - 1;
return max(max(ans[x1][y1][px][py], ans[x2 - dx][y1][px][py]),
max(ans[x1][y2 - dy][px][py], ans[x2 - dx][y2 - dy][px][py]));
}
bool ok(int mid, int x1, int y1, int x2, int y2) {
if (mid == 0) return true;
return query(x1 + mid - 1, y1 + mid - 1, x2, y2) >= mid;
}
int main() {
init();
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &data[i][j]);
}
}
solve();
int q;
scanf("%d", &q);
cal();
while (q--) {
int x1, y1, x2, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
int l = 0, r = min(y2 - y1 + 1, x2 - x1 + 1), ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (ok(mid, x1, y1, x2, y2)) {
l = mid + 1;
ans = mid;
} else {
r = mid - 1;
}
}
printf("%dn", ans);
}
}
|
近期评论