Problema Wordsearch risultato non corretto

Avrei bisogno di un aiutino a risolvere wordsearch, stranamente il problema non è il tempo (il subtask 6 è tutto corretto), ma un paio di sottoposizioni nel subtask 2 e 3 che danno risultato sbagliato.
Ho provato a sottoporre un po’ di input “scomodi” ma il programma sembra dare sempre la risposta corretta.
Qualcuno ha idea di quale potrebbe essere il problema?

Non abbiamo la sfera di cristallo :wink: passa il codice

Giusto.
Uso la programmazione dinamica con un vettore in 3 dimensioni (2 per la posizione nella griglia e una per la posizione all’interno della stringa da ricercare) e per velocizzare il tutto memorizzo in un vettore che posizione hanno le varie lettere che mi interessano (anche se ribadisco che il mio problema non è il tempo).

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

int main(){
ifstream in("input.txt");
ofstream out("output.txt");
long long int n,m, lun,r,c,ris=0;
string s;
vector<string> griglia;
vector<vector<pair<int,int> > > track;
vector<bool> lettere;
vector<vector<vector<int> > > dp;

in >> s >> n >> m;
griglia.resize(n);
for(int i=0;i<n;i++)
    in >> griglia[i];
lun=s.size();

track.resize(26);
lettere.resize(26,false);
for(int i=0;i<s.size();i++)
    lettere[s[i]-'a']=true;

for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        if(lettere[griglia[i][j]-'a'])
            track[griglia[i][j]-'a'].push_back(make_pair(i,j));
    }
}

dp.resize(lun);
for(int i=0;i<lun;i++){
    dp[i].resize(n);
    for(int j=0;j<n;j++)
        dp[i][j].resize(m,0);
}

for(int i=lun-1;i>0;i--){
    for(int j=0;j<track[s[i]-'a'].size();j++){
        r=track[s[i]-'a'][j].first;
        c=track[s[i]-'a'][j].second;

        //alto sx
        if(r>0 && c >0){
            if(griglia[r-1][c-1]==s[i-1]){
                dp[i-1][r-1][c-1]=(dp[i-1][r-1][c-1]+dp[i][r][c])%MOD;
                if(i==lun-1)
                    dp[i-1][r-1][c-1]=(dp[i-1][r-1][c-1]+1)%MOD;
            }
        }

        //alto
        if(r>0){
            if(griglia[r-1][c]==s[i-1]){
                dp[i-1][r-1][c]=(dp[i-1][r-1][c]+dp[i][r][c])%MOD;
                if(i==lun-1)
                    dp[i-1][r-1][c]=(dp[i-1][r-1][c]+1)%MOD;
            }
        }

        //alto dx
        if(r>0 && c<m-1){
            if(griglia[r-1][c+1]==s[i-1]){
                dp[i-1][r-1][c+1]=(dp[i-1][r-1][c+1]+dp[i][r][c])%MOD;
                if(i==lun-1)
                    dp[i-1][r-1][c+1]=(dp[i-1][r-1][c+1]+1)%MOD;
            }
        }

        //dx
        if(c <m-1){
            if(griglia[r][c+1]==s[i-1]){
                dp[i-1][r][c+1]=(dp[i-1][r][c+1]+dp[i][r][c])%MOD;
                if(i==lun-1)
                    dp[i-1][r][c+1]=(dp[i-1][r][c+1]+1)%MOD;
            }
        }

        //basso dx
        if(r<n-1 && c<m-1){
            if(griglia[r+1][c+1]==s[i-1]){
                dp[i-1][r+1][c+1]=(dp[i-1][r+1][c+1]+dp[i][r][c])%MOD;
                if(i==lun-1)
                    dp[i-1][r+1][c+1]=(dp[i-1][r+1][c+1]+1)%MOD;
            }
        }

        //basso
        if(r<n-1){
            if(griglia[r+1][c]==s[i-1]){
                dp[i-1][r+1][c]=(dp[i-1][r+1][c]+dp[i][r][c])%MOD;
                if(i==lun-1)
                    dp[i-1][r+1][c]=(dp[i-1][r+1][c]+1)%MOD;
            }
        }

        //basso sx
        if(r<n-1 && c >0){
            if(griglia[r+1][c-1]==s[i-1]){
                dp[i-1][r+1][c-1]=(dp[i-1][r+1][c-1]+dp[i][r][c])%MOD;
                if(i==lun-1)
                    dp[i-1][r+1][c-1]=(dp[i-1][r+1][c-1]+1)%MOD;
            }
        }

        //sx
        if( c >0){
            if(griglia[r][c-1]==s[i-1]){
                dp[i-1][r][c-1]=(dp[i-1][r][c-1]+dp[i][r][c])%MOD;
                if(i==lun-1)
                    dp[i-1][r][c-1]=(dp[i-1][r][c-1]+1)%MOD;
            }
        }

    }
}

/*for(int i=0;i<lun;i++){
    for(int j=0;j<n;j++){
        for(int k=0;k<m;k++)
            cout<<dp[i][j][k]<<" ";
        cout<<endl;
    }
    cout<<endl;
}*/

for(int i=0;i<track[s[0]-'a'].size();i++){
    r=track[s[0]-'a'][i].first;
    c=track[s[0]-'a'][i].second;
    ris=(ris+dp[0][r][c])%MOD;
}

out<<ris;

}