問題
http://topcoder.bgcoder.com/print.php?id=975
アルファベットＡ～Ｚからなる配列が与えられる。
長さlengthが与えられ、このときAを長さ1とし、B,C,,,と長さ分の連続したアルファベットを作りたい。
連続したアルファベットを作る際には、配列の任意の文字からスタートして、縦横斜めに一つずつ移動することができる。
このとき、作ることのできる連続したアルファベットは何通りあるか求める。
ただし、１０＾９通り以上ある場合は１０＾９を返す。
解き方
ｄｐで解く問題。ただし、１０＾９を超えているかチェックし超えていればそこで打ち切る処理が必要。
ｄｐ＝０で初期化すると実装はより簡単だが、探索して何もなかったときの判定ができないので計算量が間に合わない場合がある。
そのため、ｄｐ＝ー１で初期化して探索済みの場合は０以上になるようにした。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int length,w,h;
int p[60][60];
long long dp[60][60];
class AlphabetCount {
public:
int rec(int r,int c,int len){
if(dp[r][c]!=-1)return dp[r][c];
if(len==length-1)return dp[r][c]=1;
long long ret=0;
for(int i=r-1;i<=r+1;i++)for(int j=c-1;j<=c+1;j++){
if(0<=i && i<h && 0<=j && j<w && p[i][j]==len+1){
ret+=rec(i,j,len+1);
if(ret>1000000000)return 1000000000;
}
}
return dp[r][c]=ret;
}
int count(vector<string> grid, int length_) {
length=length_;
h=grid.size();
w=grid[0].size();
memset(dp,-1,sizeof(dp));
FORE(i,0,h)FORE(j,0,w)p[i][j]=grid[i][j]-'A';
long long ret=0;
FORE(i,0,h)FORE(j,0,w)if(p[i][j]==0){
ret+=rec(i,j,0);
if(ret>1000000000)return 1000000000;
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int length,w,h;
int p[60][60];
long long dp[60][60];
class AlphabetCount {
public:
int rec(int r,int c,int len){
if(dp[r][c]!=-1)return dp[r][c];
if(len==length-1)return dp[r][c]=1;
long long ret=0;
for(int i=r-1;i<=r+1;i++)for(int j=c-1;j<=c+1;j++){
if(0<=i && i<h && 0<=j && j<w && p[i][j]==len+1){
ret+=rec(i,j,len+1);
if(ret>1000000000)return 1000000000;
}
}
return dp[r][c]=ret;
}
int count(vector<string> grid, int length_) {
length=length_;
h=grid.size();
w=grid[0].size();
memset(dp,-1,sizeof(dp));
FORE(i,0,h)FORE(j,0,w)p[i][j]=grid[i][j]-'A';
long long ret=0;
FORE(i,0,h)FORE(j,0,w)if(p[i][j]==0){
ret+=rec(i,j,0);
if(ret>1000000000)return 1000000000;
}
return ret;
}
};
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class AlphabetCount {
public:
int count(vector<string> grid, int length) {
int h=grid.size();
int w=grid[0].size();
long long dp[h][w];
memset(dp,0,sizeof(dp));
FORE(i,0,h)FORE(j,0,w)if(grid[i][j]=='A')dp[i][j]=1;
FORE(i,1,length){
char ch='A'+i;
FORE(j,0,h)FORE(k,0,w){
if(grid[j][k]==ch){
FORE(r,j-1,j+2)FORE(c,k-1,k+2){
if(0<=r && r<h && 0<=c && c<w && grid[r][c]==(ch-1)){
dp[j][k]=min((long long)1e+9,dp[j][k]+dp[r][c]);
}
}
}
}
}
long long ret=0;
FORE(i,0,h)FORE(j,0,w){
if(grid[i][j]==('A'+length-1))ret+=dp[i][j];
}
return ret>=1e+9 ? 1e+9 : ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class AlphabetCount {
public:
int count(vector<string> grid, int length) {
int h=grid.size();
int w=grid[0].size();
long long dp[h][w];
memset(dp,0,sizeof(dp));
FORE(i,0,h)FORE(j,0,w)if(grid[i][j]=='A')dp[i][j]=1;
FORE(i,1,length){
char ch='A'+i;
FORE(j,0,h)FORE(k,0,w){
if(grid[j][k]==ch){
FORE(r,j-1,j+2)FORE(c,k-1,k+2){
if(0<=r && r<h && 0<=c && c<w && grid[r][c]==(ch-1)){
dp[j][k]=min((long long)1e+9,dp[j][k]+dp[r][c]);
}
}
}
}
}
long long ret=0;
FORE(i,0,h)FORE(j,0,w){
if(grid[i][j]==('A'+length-1))ret+=dp[i][j];
}
return ret>=1e+9 ? 1e+9 : ret;
}
};