問題
http://community.topcoder.com/stat?c=problem_statement&pm=10268&rd=13696
1桁の数字がかかれた２次元のセルが与えられる。
各列、行番号についてそれぞれ等差数列になるように任意の数字を連結させることができる。
連結した数字のうち、それがある数の２乗になるようなもののうち
最大のものを求める。
解き方
すべての位置について、列番号、行番号それぞれについてとりうる
等差数列すべてを調べてあげればよい。
2乗の確認はdoubleでは確かめられなく、整数型にすることに注意。
コード
class FindingSquareInTable {
public:
long long tolong(string str){
stringstream out(str);
long long num;
out>>num;
return num;
}
int findMaximalSquare(vector<string> table) {
int h=table.size(),w=table[0].size();
long long ret=-1;
FORE(i,0,h)FORE(j,0,w){
for(int dr=-h;dr<=h;dr++)for(int dc=-w;dc<=w;dc++){
if(dr==0&&dc==0)continue;
string str="";
int r=i,c=j;
while(0<=r && r<h && 0<=c && c<w){
str+=table[r][c];
r+=dr,c+=dc;
long long num=tolong(str);
if((long long)sqrt(num)*(long long)sqrt(num)==num)ret=max(ret,num);
}
}
}
return ret;
}
};
public:
long long tolong(string str){
stringstream out(str);
long long num;
out>>num;
return num;
}
int findMaximalSquare(vector<string> table) {
int h=table.size(),w=table[0].size();
long long ret=-1;
FORE(i,0,h)FORE(j,0,w){
for(int dr=-h;dr<=h;dr++)for(int dc=-w;dc<=w;dc++){
if(dr==0&&dc==0)continue;
string str="";
int r=i,c=j;
while(0<=r && r<h && 0<=c && c<w){
str+=table[r][c];
r+=dr,c+=dc;
long long num=tolong(str);
if((long long)sqrt(num)*(long long)sqrt(num)==num)ret=max(ret,num);
}
}
}
return ret;
}
};