USACO Training Section 3.3 Home on the Range

英文原题  中文题译

大意：给定一个01矩阵，计算其中全为１的方形子块的个数并按方块的边长计数分别输出。

矩阵大小不超过250，The simple the best，直接枚举。
1.首先读入矩阵后将数值取反，这样，在判断矩阵内是否有0变成判断是否有1，只需判断其元素和是否为即可，不需计算矩阵面积。
2.计数sum[i][j]为(1,1)到(i,j)的矩形区域内的元素之和，用递推式计算。注意这里我用了1..n_size作为坐标，而不是通常的0..(nsize-1)，这样可以避免计算中判断ir-1,ic-1是否小于0。不过别忘了在初始化也要这样。
3.从每个ir,ic坐标开始往下生成方块，并计数，如果某个方块内元素之和大于0，则比它更大的也一定如此，就不需再计算了。
4.输出。

这恐怕是最简洁的方法了。由于矩阵内容是不变的，可以应用。如果矩阵内容变化，则需考虑用树状数组这样的复杂结构来保证计算的效率了。另外，在第三步中，逐个扫描也可换成二分扫描，不过，复杂度照样是O(n^3)而非O(n^2logn)，原因：计数最坏需O(n)复杂度。

/*
ID: blackco3
TASK: range
LANG: C++
*/
#include <iostream>
#include <memory.h>
using namespace std;
const int _max_len_(250) ;
int n_size, mtrx[_max_len_+1][_max_len_+1], sum[_max_len_+1][_max_len_+1], squares[_max_len_] ;

int main() {
	freopen("range.in", "r", stdin);
	freopen("range.out", "w", stdout);
	cin >> n_size ;
	char line[_max_len_+1] ;
	for( int ir=1; ir<=n_size; ir++ ){
		cin >> line ;
		for( int ic=1; ic<=n_size; ic++ )
			mtrx[ir][ic] = 1-(line[ic-1] - '0') ;
	}
	memset( sum, 0, sizeof(sum) );
	memset( squares, 0, sizeof(squares) );
	for( int ir=1; ir<=n_size; ir++ )
		for( int ic=1; ic<=n_size; ic++ )
			sum[ir][ic]  = mtrx[ir][ic] + sum[ir-1][ic] + sum[ir][ic-1] - sum[ir-1][ic-1] ;
	for( int ir=1; ir<=n_size; ir++ )
		for( int ic=1; ic<=n_size; ic++ ){
			int max_len = ir>ic ? n_size-ir : n_size-ic ;
			for( int len=1; len<=max_len; len++ ){
				if( sum[ir+len][ic+len] + sum[ir-1][ic-1] - sum[ir+len][ic-1] -sum[ir-1][ic+len] )
					break ;
				squares[len]++ ;
			}
		}
	for( int len=1; len<n_size; len++ )
		if( squares[len] )
			cout << len + 1 << " "  << squares[len] << endl ;
	return 0;
}