Everyone on the internet says to preprocess first, the key is how to preprocess. I don't know~~~
But here I finally understand some
-
First calculate how many rectangles can be formed with each cell and the cell above it, and change 1 to 0 when encountered.
-
Then use a large enumeration of four directions u, l, d, r to calculate the maximum number of rectangles that can be formed with the cells within these four directions from the bottom right corner.
So as long as you add the points calculated in the first step to the current minimum value, don't calculate again when encountering 0.
- Add the number of u, l, d-1, r and u, l, d, r-1, of course, these have already been processed (and these processed points have also been processed (DP concept)), and because there may be overlapping parts, u, l, d-1, r-1 must be subtracted.
/\*
\* GCA : "Computer is artificial subject absolutely,Math is God"
\*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
#include <ctime>
using namespace std;
#ifdef DEBUG
#define VAR(a,b) \_\_typeof(b) a=(b)
#define debug(...) printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)
#else
#define VAR(a,b) \_\_typeof(b) a=(b)
#define debug(...)
#endif
typedef unsigned int uint;
typedef long long int Int;
typedef unsigned long long int UInt;
#define Set(a,s) memset(a,s,sizeof(a))
#define Pln() printf("\\n")
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define M 45
#define PB push\_back
#define oo INT\_MAX
#define FOR(a,b) for(VAR(a,(b).begin());a!=(b).end();++a)
#define eps 1e-9
#define X first
#define Y second
inline bool xdy(double x,double y){return x>y+eps;}
inline bool xddy(double x,double y){return x>y-eps;}
inline bool xcy(double x,double y){return x<y-eps;}
inline bool xcdy(double x,double y){return x<y+eps;}
const Int mod=1000000007;
int n,m,q;
char mz\[M\]\[M\];
int dp\[M\]\[M\]\[M\]\[M\];
int cnt\[M\]\[M\];
void pre(){
Set(dp,0);
Set(cnt,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mz\[i-1\]\[j-1\]=='0')cnt\[i\]\[j\]=cnt\[i-1\]\[j\]+1;
else cnt\[i\]\[j\]=0;
}
}
for(int u=1;u<=n;u++){
for(int l=1;l<=m;l++){
for(int d=u;d<=n;d++){
for(int r=l;r<=m;r++){
int minn=d-u+1;
int all=0;
for(int k=r;k>=l;k--){
minn=min(minn,cnt\[d\]\[k\]);
if(minn==0)break;
all+=minn;
}
dp\[u\]\[l\]\[d\]\[r\]=dp\[u\]\[l\]\[d-1\]\[r\]+dp\[u\]\[l\]\[d\]\[r-1\]-dp\[u\]\[l\]\[d-1\]\[r-1\]+all;
}
}
}
}
}
int main() {
ios\_base::sync\_with\_stdio(0);
while(~scanf("%d%d%d",&n,&m,&q)){
for(int i=0;i<n;i++){
scanf("%s",mz\[i\]);
}
pre();
while(q--){
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
printf("%d\\n",dp\[a\]\[b\]\[c\]\[d\]);
}
}
}