harshraj22's blog

By harshraj22, history, 5 years ago, In English

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);
        }

};

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?