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