プロジェクトオイラー問147 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20147
Problem 147 「斜交平行格子内の長方形」 †
縦線と対角線を引いた正方形をｎ*ｍの形で配置する。
47*43までのサイズに何個の長方形が存在するか数えよ。

多分漸化式で計算すると思いますが、一個ずつ数えました。
計算時間２０秒。
かなり遅い処理です。

#include<stdio.h>
#include<map>
#include<algorithm>
#include<iostream>

struct E{
	int x,y;
	bool operator<(const E& e1)const{
		if(x!=e1.x)return x<e1.x;
		return y<e1.y;
	}
}; 

__int64 ans=0;


void g(std::map<E,__int64>& ms,E e1,__int64 n){
	if(ms.find(e1)==ms.end()){
		return ;
	}else{
		ans+=std::min(ms[e1],n);
		//std::cout<<ms[e1]<<" "<<n<<" "<<e1.x<<" "<<e1.y<<"\n";
		e1.x--;
		e1.y++;
		g(ms,e1,n);
	}
}

int f(std::map<E,__int64>& ms,E e1){
	if(ms.find(e1)==ms.end()){
		return 0;
	}else{
		e1.x++;
		e1.y++;
		int r=f(ms,e1);
		e1.x--;
		e1.y--;
		ms[e1]=r;
		return r+1;
	}
}

void calc(int r,int c){
	E e1;
	std::map<E,__int64> ms;
	for(int i=0;i<=r;i++){
		for(int j=0;j<=c;j++){
			e1.y=i*2;
			e1.x=j*2;
			ms[e1]=0;
		}
	}
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			e1.y=i*2+1;
			e1.x=j*2+1;
			ms[e1]=0;
		}
	}
	for(int i=0;i<=r;i++){
		e1.y=i*2;
		e1.x=0;
		f(ms,e1);	
	}
	for(int i=0;i<=c;i++){
		e1.y=0;
		e1.x=i*2;
		f(ms,e1);
	}
	for(std::map<E,__int64>::iterator it=ms.begin();it!=ms.end();it++){
		e1=(*it).first;
		e1.x--;
		e1.y++;
		g(ms,e1,(*it).second);
	}
	ans+=((__int64)r*(r+1)*c*(c+1))/4;
}

int main(){
	for(int r=1;r<=47;r++){
		for(int c=1;c<=43;c++){
			calc(r,c);
			//std::cout<<ans<<"\n";
		}
	}
	std::cout<<ans<<"\n";
}