### Rectangles in cross-hatched grids题号：147 难度： 65 中英对照

In a 3x2 cross-hatched grid, a total of 37 different rectangles could be situated within that grid as indicated in the sketch.

There are 5 grids smaller than 3x2, vertical and horizontal dimensions being important, i.e. 1x1, 2x1, 3x1, 1x2 and 2x2. If each of them is cross-hatched, the following number of different rectangles could be situated within those smaller grids:

1x1: 1
2x1: 4
3x1: 8
1x2: 4
2x2: 18

Adding those to the 37 of the 3x2 grid, a total of 72 different rectangles could be situated within 3x2 and smaller grids.

How many different rectangles could be situated within 47x43 and smaller grids?

### Code

public final class p147 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

static public String run() {
long ans=0;
final int n=47,m=43;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
ans+=get(i,j);
return ""+ans;
}

static public int get(int n,int m){
int res=0;
//正规的
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
res+=(n-i+1)*(m-j+1);
//斜着的
int size=n+m;
boolean[][] flag=new boolean[size][size];
for(int i=0;i<size;i++) for(int j=0;j<size;j++){
if(i+j>=n && i+j<n+m+m-1
&& size-i+j>m
&& size-i+j<m+n+n)
flag[i][j]=true;
else
flag[i][j]=false;
}
for(int i=0;i<size;i++) for(int j=0;j<size;j++){
if(flag[i][j]){
for(int ii=i;ii<size;ii++) for(int jj=j;jj<size;jj++){
if(flag[ii][j] && flag[i][jj] && flag[ii][jj])
res++;
else
break;
}
}
}
return res;
}
}
846910284
897ms