当前位置:首页 » Project Euler » 详细页

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?


Solution

对于给定的$n$行$m$列的格子,只需要计算所有$1\leq i \leq n, 1\leq j \leq m$的$i$行$j$列的格子的“矩形数量”即为答案。 $n$行$m$列的格子包含的“矩形数量”计算方法如下: 1. 横平竖直的方格,直接枚举所有$1\leq i \leq n, 1\leq j \leq m$,直接求和$(n-i+1)\times(m-j+1)$即可。 2. 斜着的方格,考虑先将其旋转45度后,正过来计算。用一个boolean矩阵来标记当前斜着的方格是否真实存在,则这个矩阵需要有$n+m$行$n+m$列,之后用两层循环枚举矩形左上角点,再用两层循环枚举矩形右下角点,要求内部所有点对应的boolean矩阵都为true即将计数器加一。 注明: 当2行3列时,斜着的boolean矩阵如下(用0代表false,1代表true): 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 中间部分即为旋转45度后正过来的“斜方格”。

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