I was trying BoggleScore problem from topcoder. I tried dp approach, saving answer to each substring at each cell. I am getting WA, and can't understand why. Can anyone help me ? Here is my code :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
long long int mod = 1e13,hashi=1;
const int N = 3e5+5;
vector<ll> dp[6][6];
unordered_map<string,ll> mp;
ll getHash(string s){
if(mp[s] != 0)
return mp[s];
mp[s] = hashi++;
return mp[s];
}
vector<string> grid;
ll obtain(ll i,ll j,string s){
// termination case, if i or j is out of grid
if(i<0 || j<0)
return 0;
else if(i>=4 || j>=4)
return 0;
ll hsh = getHash(s);
if(s.size()==0)
return dp[i][j][hsh] = 0;
else if(grid[i][j] != s[0]){
return dp[i][j][hsh] = 0;
}
if(dp[i][j][hsh] != -1){
return dp[i][j][hsh];
}
else if(s.size()==1 && grid[i][j] == s[0]){
return dp[i][j][hsh] = 1;
}
dp[i][j][hsh] = 0;
s = s.substr(1,(ll)s.size()-1);
for(int ii=-1;ii<2;ii++){
for(int jj=-1;jj<2;jj++){
if(ii == 0 && jj == 0)
continue;
dp[i][j][hsh] += obtain(i+ii,j+jj,s);
dp[i][j][hsh] %= mod;
}
}
return dp[i][j][hsh]%mod;
}
long long int solve(vector<string> &input){
ll ans = 0;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
for(auto s:input){
ans += obtain(i,j,s)*s.size()*s.size();
ans %= mod;
}
}
}
return ans%mod;
}
class BoggleScore{
public:
ll bestScore(vector<string> grd, vector<string>input){
for(int i=0;i<6;i++){
for(int j=0;j<6;j++)
dp[i][j].resize(N,-1);
}
mp.clear(); grid = grd;
return solve(input);
}
};