Ho fatto il problema del wordsearch con una ricorsione salvando i risultati parziali su un matrice tridimensionale sia nel caso in cui ci sia una risposta che nel caso in cui non riesca a trovare una risposta cosi da ridurre i tempi il più possibile, qualcuno di voi ha idea di cosa devo implementare per riuscire a risolvere l’ultimo testcase dell’ultimo subtask ?
Quello chè hai fatto dovrebbe bastare, prova a postare il codice , così è più facile aiutarti
1 Mi Piace
#include <stdio.h>
#include <string.h>
#define MAXH 100
#define MAXW 100
#define MAXS 1000
char S[MAXS + 1];
int H, W;
char M[MAXH][MAXW + 1];
int tmp[MAXH][MAXW][MAXS] = {0};
int indici1[MAXH*MAXW][2];
int indici2[MAXH*MAXW][2];
int *sol[MAXS];
int cnt = 0;
void SEARCHwordR(int i, int j, int indice);
int main() {
char tmp;
int lunS;
if (scanf("%s", S) != 1)return 0;
if (scanf("%d %d", &H, &W) != 2 || H < 1 || W > 100)return 0;
lunS=strlen(S);
int i, j, lun1,lun2;
for (i = 0; i < H; i++) {
if (scanf("%s", M[i]) != 1)return 0;
}
lun1=0;lun2=0;
for(i=0;i<MAXH;i++){
for(j=0;j<MAXW;j++){
if(S[0]==M[i][j]){
indici1[lun1][0]=i;
indici1[lun1][1]=j;
lun1++;
}
if(S[lunS-1]==M[i][j]){
indici2[lun2][0]=i;
indici2[lun2][1]=j;
lun2++;
}
}
}
if(lun1==0||lun2==0) {
printf("%d", cnt);
return 0;
}
if(lun1>lun2){
for(i=0,j=lunS-1;i<lunS/2;j--,i++){
tmp=S[i];
S[i]=S[j];
S[j]=tmp;
}
for(i=0;i<lun2;i++){
SEARCHwordR(indici2[i][0],indici2[i][1],1);
}
}
else{
for(i=0;i<lun1;i++){
SEARCHwordR(indici1[i][0],indici1[i][1],1);
}
}
printf("%d\n", cnt);
return 0;
}
void SEARCHwordR(int i, int j, int indice) {
int k;
if (S[indice] == '\0') {
for (k = 1; k < indice - 1; k++) {
*sol[k] = (1 + *sol[k]) % 1000000007;
}
cnt = (cnt + 1) % 1000000007;
return;
}
if (indice != 1) {
sol[indice - 1] = &tmp[i][j][indice - 1];
}
if (i - 1 >= 0 && M[i - 1][j] == S[indice] && tmp[i - 1][j][indice] != -1) {//controllo in alto
if (tmp[i - 1][j][indice] > 0) {
cnt = (cnt + tmp[i - 1][j][indice]) % 1000000007;
for (k = 1; k < indice; k++) {
*sol[k] = (*sol[k] + tmp[i - 1][j][indice]) % 1000000007;
}
} else {
SEARCHwordR(i - 1, j, indice + 1);
}
}
if (i + 1 < H && M[i + 1][j] == S[indice] && tmp[i + 1][j][indice] != -1) {//controllo in basso
if (tmp[i + 1][j][indice] > 0) {
cnt = (cnt + tmp[i + 1][j][indice]) % 1000000007;
for (k = 1; k < indice; k++) {
*sol[k] = (*sol[k] + tmp[i + 1][j][indice]) % 1000000007;
}
} else {
SEARCHwordR(i + 1, j, indice + 1);
}
}
if (j - 1 >= 0 && M[i][j - 1] == S[indice] && tmp[i][j - 1][indice] != -1) {//controllo a sinistra
if (tmp[i][j - 1][indice] > 0) {
cnt = (cnt + tmp[i][j - 1][indice]) % 1000000007;
for (k = 1; k < indice; k++) {
*sol[k] = (*sol[k] + tmp[i][j - 1][indice]) % 1000000007;
}
} else {
SEARCHwordR(i, j - 1, indice + 1);
}
}
if (j + 1 < W && M[i][j + 1] == S[indice] && tmp[i][j + 1][indice] != -1) {//controllo a destra
if (tmp[i][j + 1][indice] > 0) {
cnt = (cnt + tmp[i][j + 1][indice]) % 1000000007;
for (k = 1; k < indice; k++) {
*sol[k] = (*sol[k] + tmp[i][j + 1][indice]) % 1000000007;
}
} else {
SEARCHwordR(i, j + 1, indice + 1);
}
}
if (i - 1 >= 0 && j + 1 < W &&
M[i - 1][j + 1] == S[indice] && tmp[i - 1][j + 1][indice] != -1) {//controllo diagonale in alto a destra
if (tmp[i - 1][j + 1][indice] > 0) {
cnt = (cnt + tmp[i - 1][j + 1][indice]) % 1000000007;
for (k = 1; k < indice; k++) {
*sol[k] = (*sol[k] + tmp[i - 1][j + 1][indice]) % 1000000007;
}
} else {
SEARCHwordR(i - 1, j + 1, indice + 1);
}
}
if (i - 1 >= 0 && j - 1 >= 0 &&
M[i - 1][j - 1] == S[indice] && tmp[i - 1][j - 1][indice] != -1) {//controllo diagonale in alto a sinistra
if (tmp[i - 1][j - 1][indice] > 0) {
cnt = (cnt + tmp[i - 1][j - 1][indice]) % 1000000007;
for (k = 1; k < indice; k++) {
*sol[k] = (*sol[k] + tmp[i - 1][j - 1][indice]) % 1000000007;
}
} else {
SEARCHwordR(i - 1, j - 1, indice + 1);
}
}
if (i + 1 < H && j + 1 < W &&
M[i + 1][j + 1] == S[indice] && tmp[i + 1][j + 1][indice] != -1) {//controllo diagonale in basso a destra
if (tmp[i + 1][j + 1][indice] > 0) {
cnt = (cnt + tmp[i + 1][j + 1][indice]) % 1000000007;
for (k = 1; k < indice; k++) {
*sol[k] = (*sol[k] + tmp[i + 1][j + 1][indice]) % 1000000007;
}
} else {
SEARCHwordR(i + 1, j + 1, indice + 1);
}
}
if (i + 1 < H && j - 1 >= 0 &&
M[i + 1][j - 1] == S[indice] && tmp[i + 1][j - 1][indice] != -1) {//controllo diagonale in bassso a sinistra
if (tmp[i + 1][j - 1][indice] > 0) {
cnt = (cnt + tmp[i + 1][j - 1][indice]) % 1000000007;
for (k = 1; k < indice; k++) {
*sol[k] = (*sol[k] + tmp[i + 1][j - 1][indice]) % 1000000007;
}
} else {
SEARCHwordR(i + 1, j - 1, indice + 1);
}
}
if (indice != 1 && tmp[i][j][indice - 1] == 0) {
tmp[i][j][indice - 1] = -1;
}
}
ho aggiunto qualcosa per provare, del tipo controllare quale lettera tra la prima e l’ultima compare più volte e nel caso non dovesse comparire una delle due uscire dal programma se invece dovessero comparire entrambi iniziare la ricerca da quella che compare meno volte quindi nel caso l’ultima lettera della parola compare meno volte della prima inverto la parola e cerco la parola invertita.
La tabella della memoizzazione è inizializzata a 0?
1 Mi Piace
Si certo, come ho detto il programma funzione ma non risolve lultimo testcase dell ultimo subtask
quali controlli hai fatto per farlo andare più velocemente ?
Il fatto che la matrice sia inizializzata a 0 rallenta di molto l’esecuzione, perché può darsi che partendo da una certa casella non si trovino parole.
Il tuo programma non distingue e se una determinata situazione non l hai verificata oppure l’hai verificata ma il risultato è 0.
Inizializza la matrice di memoizzazione a -1 e ricalcola solo quando la tua casella è! =-1. Spero di essere stato chiaro.
Fabio.
1 Mi Piace
non sono sicuro di aver capito bene, la mia matrice di memoizzazione è inizializzata a 0 se un una lettera prova tutte le 8 coordinate senza trovare la lettera dopo, salva nella matrice di memoizzazione -1 in questo modo:
if (indice != 1 && tmp[i][j][indice - 1] == 0) {
tmp[i][j][indice - 1] = -1;
}
quindi gli dice che se non trova nessuna soluzione di impostare l’indirizzo corrispondente a -1, mentre se trova la soluzione aumenta il counter per il numero di volte che la parola viene trovata.
In questo modo se mai una dovesse tornare sulla stessa lettera non ricalcola tutto da capo ma sa già che non troverà nessuna soluzione. Quindi ricalcola la matrice solo se è 0, quindi non ha trovato ancora nessuna soluzione mentre se è maggiore di 0 sa che troverà tante soluzioni quanto è maggiore di 0 il numero se è -1 sa che non troverà nessuna soluzione continuando su quel percorso quindi termina. Intendevi questo o stavi dicendo tutta un’altra cosa ?
Probabilmente intendeva di inizializzare a -1 i valori nella matrice della memoizzazione. Se in una cella hai salvato -1 (quando arrivi in quella determinata situazione), vuol dire che non l’hai ancora visitata. Se hai salvato 0 o qualsiasi altro numero, significa che hai già calcolato il numero di soluzioni da lì in poi. Spero di essere stato chiaro,
Filippo