Everyone on the internet says to preprocess first, the key is how to preprocess. I don't know~~~
But finally, I understand some of it now.
-
First, calculate how many rectangles can be formed with each cell and the cell above it, and change 1 to 0.
-
Then, use a large enumeration of four directions: up, left, down, right. Calculate the maximum number of rectangles that can be formed with the cells within these four directions using the bottom right corner point.
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 the points that need to be processed 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\]);
}
}
}