問題
http://community.topcoder.com/stat?c=problem_statement&pm=11934&rd=14734
解き方
３点を選んだ時、そのｘ座標の最小値と最大値の差、ｙ座標の最小値と最大値の差が
それぞれ１辺となる長方形の外周の長さが、たどるルートの長さになる。
あとはその長方形が与えられたセルでいくつつくれるか、
その長方形を作ることのできる点の組み合わせの数をかけてあげればよい。
コード
class PatrolRoute {
public: int countRoutes(int X, int Y, int minT, int maxT) {
int ret=0;
int MOD=1000000007;
for(int xlen=3;xlen<=X;xlen++)for(int ylen=3;ylen<=Y;ylen++){
int len=((xlen-1)+(ylen-1))*2;
if(minT<=len && len<=maxT){
long long sum=(xlen-2)*(ylen-2)*6;
sum=(sum*(X-xlen+1)*(Y-ylen+1))%MOD;
ret=(ret+sum)%MOD;
}
}
return ret;
}
};
public: int countRoutes(int X, int Y, int minT, int maxT) {
int ret=0;
int MOD=1000000007;
for(int xlen=3;xlen<=X;xlen++)for(int ylen=3;ylen<=Y;ylen++){
int len=((xlen-1)+(ylen-1))*2;
if(minT<=len && len<=maxT){
long long sum=(xlen-2)*(ylen-2)*6;
sum=(sum*(X-xlen+1)*(Y-ylen+1))%MOD;
ret=(ret+sum)%MOD;
}
}
return ret;
}
};