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

Problem 98 「アナグラム平方数」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2098
テキストファイルから平方アナグラム単語対を求める問題。

とりあえず全探索で答えが出ます。

#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<iostream>
#include<algorithm>
std::map<std::string,std::vector<std::string> > maps;
std::set<__int64> sq;


bool nums[10];
int toNum[256];

__int64 f2(std::string str,int p,__int64 num){
	if(p>=str.size()){
		if(sq.find(num)==sq.end())return 0;
		return num;
	}else{
		if(p==0&&toNum[str[p]]==0)return 0;
		return f2(str,p+1,num*10+toNum[str[p]]);
	}
} 

__int64 f(const std::string& str,int p,__int64 num){
	if(p>=str.size()){
		if(sq.find(num)==sq.end())return 0;
		std::string str2=str;
		std::sort(str2.begin(),str2.end());
		__int64 ans=0;
		for(std::vector<std::string>::iterator vIt=maps[str2].begin();vIt!=maps[str2].end();vIt++){
			__int64 t=f2((*vIt),0,0);
			if(t==0)return 0;
			ans=std::max(ans,t);
		}
		return ans;
	}else{
		__int64 ans=0,t;
		if(toNum[str[p]]!=-1){
			ans=f(str,p+1,num*10+toNum[str[p]]);
		}else{
		
			for(int i=0;i<=9;i++){
				if((p==0)&&(i==0))continue;
				if(nums[i]==true) continue;
				nums[i]=true;
				toNum[str[p]]=i;
				t=f(str,p+1,num*10+i);
				toNum[str[p]]=-1;
				nums[i]=false;
				
				ans=std::max(t,ans);
			}
		}
		return ans;
	}
	
}


int main(){
	for(__int64 i=1;i<100000;i++){
		sq.insert(i*i);
	}
	
	FILE *fp;
 if ((fp = fopen("words.txt", "r")) == NULL) {
        	fprintf(stderr, "%s\n", "error: can't read file.");
        	return EXIT_FAILURE;
    	}
	char text[18];
	while(fscanf(fp,"\"%[^\"]\"",text)!=EOF){
 		//printf("%s ",text);
		std::string str=text,str2;
		str2=str;
		std::sort(str.begin(),str.end());
		maps[str].push_back(str2);
		char c;
		if(fscanf(fp,"%c",&c)==EOF)break;
	}
	fclose(fp);
 	std::map<std::string,std::vector<std::string> >::iterator it;
	for(it=maps.begin();it!=maps.end();){
		std::string str=(*it).first;
		if((*it).second.size()==1){
			maps.erase(str);
			it=maps.lower_bound(str);
		}else{
			it++;
		}
	}
	std::cout<<maps.size();
	__int64 ans=0;
	for(int i=0;i<10;i++)nums[i]=false;
	memset(toNum,-1,sizeof(toNum));
 	for(it=maps.begin();it!=maps.end();it++){
		std::string str=(*((*it).second.begin()));
		__int64 t=f(str,0,0);
		ans=std::max(ans,t);
	}
	std::cout<<"\nans="<<ans<<"\n";
}