Labigriglia OIS 2016

sudden · 4 Agosto 2016, 10:30am

Salve,
Quest’anno, tra i problemi della finale delle olimpiadi italiane a squadre, è stata inserita questa traccia.
Sinceramente a me è dispiaciuto tanto per le povere formiche robot, ma sono rimasto così spiazzato che ho deciso di lasciarle in balia dell’insetticida. Questo problema, a parte codici interessanti di cui non ho nemmeno capito la traccia, mi sembra il più difficile in assoluto.

Non credo di aver mai capito del tutto il meccanismo dei problemi con griglia. Ho totalizzato 30 punti nel problema robot camminatore della seconda gara a squadre e la bellezza di 9 punti nel problema trabucco delle pre-oii 2015, questi sono i miei risultati più prestigiosi
A complicare ulteriormente le cose, in questo problema l’insetticida non viene messo in una casella per intero, così da doverla schivare e basta…ma viene messo in punti diversi di ogni casella e ci si deve passare comunque attraverso, non ho proprio idea di come fare.

Grazie mille in anticipo!

wil93 · 6 Agosto 2016, 5:28am

Ciao, se non lo hai già fatto ti consiglio vivamente di provare a risolvere il task Mappa antica, che è praticamente una versione più semplice di Labigriglia

Una volta risolto quello (o se lo hai già risolto) chiedi pure qui in caso dovessi avere difficoltà a trovare la soluzione a Labigriglia

sudden · 8 Agosto 2016, 5:57pm

Ti ringrazio del consiglio.Ho prontamente risolto mappa antica senza troppe difficoltà nel raggiungere i cento punti.
Ho cercato di cogliere le similitudini tra i due problemi…l’approccio che mi è venuto in mente è stato questo:

ho costruito una seconda griglia,le cui caselle sono ulteriormente divise in 4.Per ogni sottocasella tengo in mente la distanza minima dal punto di partenza.
Inoltre ho costruito una funzione per convertire un numero intero in un binario, così da facilitarmi la comprensione della posizione del veleno. La funzione è questa

void b2(int n,char V[])
{int c=0;
 while (n>0)
 {V[c]=n%2;
  n=n/2;
  c++;
 }
 while(c<4)
 {V[c]=0;
  c++;
 }
}

dopodiché ho memorizzato anche la posizione del veleno nella sottogriglia,che è strutturata in questa maniera

struct vel{int dj;bool p;
           vel(): dj(-1),p(false){}
           };

struct gri{vel V[4];};

gri G[1000][1000];

nel bool p ho memorizzato la posizione del veleno, ad esempio se il veleno venisse spruzzato verso l’alto G[i][j].V[0].p risulterebbe true. Nell’int dj, come ho già detto, ho memorizzato la distanza dalla casella di partenza.Ogni volta che passo da una “macrocasella” all’altra aumento questa distanza di 1, mentre se passo da una sottocasella all’altra della stessa macrocasella mi limito ad aggiornare dj solo se la sottocasella da cui mi sto spostando ha un valore dj più basso, senza incrementi.
Per schivare il veleno ho fatto dei controlli ogni volta che l’ho ritenuto necessario, ma il valore dello spigolo in basso a destra, G[N-1][M-1].V[3].dj continua a rimanere -1. Ho fatto del debug sparso ed ho visto che comunque le posizioni del veleno dovrei averle messe bene, credo che l’errore sia da qualche parte nella ricorsione. Il codice completo è abbastanza lungo, posto solo il caso della sottocella in alto a sinistra

 void gril(int i,int j,int N,int M,int a)
{int temp,te,t;
 if(a==0)
 {if(j-1>=0&&(G[i][j-1].V[1].dj==-1 || G[i][j-1].V[1].dj>G[i][j].V[0].dj+1))
  {G[i][j-1].V[1].dj=G[i][j].V[0].dj+1;
   temp=j-1;
   t=1;
   gril(i,temp,N,M,t);
  }
  if(j-1>=0&&(G[i][j-1].V[3].dj==-1 || G[i][j-1].V[3].dj>G[i][j].V[0].dj+1))
  if(G[i][j].V[3].p==false || G[i][j-1].V[1].p==false)
  {G[i][j-1].V[3].dj=G[i][j].V[0].dj+1;
   temp=j-1;
   
   t=3;
   gril(i,temp,N,M,t);
  }
  if(j-1>=0&&i-1>=0&&(G[i-1][j-1].V[3].dj==-1||G[i-1][j-1].V[3].dj>G[i][j].V[0].dj+1))
  {G[i-1][j-1].V[3].dj=G[i][j].V[0].dj+1;
   //cout<<G[i-1][j-1].V[3].dj<<endl;
   temp=i-1; te=j-1;
   t=3;
   gril(temp,te,N,M,t);
  }
  if(i-1>=0&&(G[i-1][j].V[2].dj==-1||G[i-1][j].V[2].dj>G[i][j].V[0].dj+1))
  {G[i-1][j].V[2].dj=G[i][j].V[0].dj+1;
   temp=i-1; t=2;
   gril(temp,j,N,M,t);
  }
  if(i-1>=0&&(G[i-1][j].V[3].dj==-1||G[i-1][j].V[3].dj>G[i][j].V[0].dj+1))
  if(G[i][j].V[0].p==false||G[i-1][j].V[2].p==false)
  {G[i-1][j].V[3].dj=G[i][j].V[0].dj+1;
   temp=i-1;t=3;
   gril(temp,j,N,M,t);
  }
  t=1;
  if(G[i][j].V[0].p==false&&G[i][j].V[1].dj==-1)
  gril(i,j,N,M,t);
  else if(G[i][j].V[1].dj>G[i][j].V[0].dj)
  {G[i][j].V[1].dj=G[i][j].V[0].dj;
   gril(i,j,N,M,t);
  }
  t=2;
  if(G[i][j].V[3].p==false&&G[i][j].V[2].dj==-1)
  gril(i,j,N,M,t);
  else if(G[i][j].V[2].dj>G[i][j].V[0].dj)
  {G[i][j].V[2].dj=G[i][j].V[0].dj;
   gril(i,j,N,M,t);
  }
 }

MrBrionix · 8 Agosto 2016, 7:00pm

L’idea di suddividere ogni casella in 4 parti è molto buona.
Anche se è molto lungo, potresti postare tutto il codice completo? Capire dov’è l’errore guardando solo un pezzetto non è molto facile considerando che magari non è neanche in quel pezzo (al momento il tuo codice mi sembra ok).

sudden · 8 Agosto 2016, 7:21pm

Ciao Brionix,
questo è il codice completo

#include <iostream>
#include <cstdlib>
using namespace std;
struct vel{int dj;bool p;
           vel(): dj(-1),p(false){}
           };
struct gri{vel V[4];};
gri G[1000][1000]; 
int griglia[1000][1000];
int N,M;
char g[4];
void b2(int n,char V[])
{int c=0;
 while (n>0)
 {V[c]=n%2;
  n=n/2;
  c++;
 }
 while(c<4)
 {V[c]=0;
  c++;
 }
}
void gril(int i,int j,int N,int M,int a)
{int temp,te,t;
 if(a==0)
 {//cout<<G[i][j].V[0].q<<" ";
 
  //cout<<G[i][j].V[0].q<<" ";
  if(j-1>=0&&(G[i][j-1].V[1].dj==-1 || G[i][j-1].V[1].dj>G[i][j].V[0].dj+1))
  {G[i][j-1].V[1].dj=G[i][j].V[0].dj+1;
   //cout<<i<<j<<endl;
   temp=j-1;
   t=1;
   gril(i,temp,N,M,t);
  }
  if(j-1>=0&&(G[i][j-1].V[3].dj==-1 || G[i][j-1].V[3].dj>G[i][j].V[0].dj+1))
  if(G[i][j].V[3].p==false || G[i][j-1].V[1].p==false)
  {G[i][j-1].V[3].dj=G[i][j].V[0].dj+1;
   temp=j-1;
   //cout<<G[i][j-1].V[3].dj<<endl;
   t=3;
   gril(i,temp,N,M,t);
  }
  if(j-1>=0&&i-1>=0&&(G[i-1][j-1].V[3].dj==-1||G[i-1][j-1].V[3].dj>G[i][j].V[0].dj+1))
  {G[i-1][j-1].V[3].dj=G[i][j].V[0].dj+1;
   //cout<<G[i-1][j-1].V[3].dj<<endl;
   temp=i-1; te=j-1;
   t=3;
   gril(temp,te,N,M,t);
  }
  if(i-1>=0&&(G[i-1][j].V[2].dj==-1||G[i-1][j].V[2].dj>G[i][j].V[0].dj+1))
  {G[i-1][j].V[2].dj=G[i][j].V[0].dj+1;
   //cout<<G[i-1][j].V[2].dj<<endl;
   temp=i-1; t=2;
   gril(temp,j,N,M,t);
  }
  if(i-1>=0&&(G[i-1][j].V[3].dj==-1||G[i-1][j].V[3].dj>G[i][j].V[0].dj+1))
  if(G[i][j].V[0].p==false||G[i-1][j].V[2].p==false)
  {G[i-1][j].V[3].dj=G[i][j].V[0].dj+1;
   //cout<<G[i-1][j].V[3].dj<<endl;
   temp=i-1;t=3;
   gril(temp,j,N,M,t);
  }
  t=1;
  if(G[i][j].V[0].p==false&&G[i][j].V[1].dj==-1)
  gril(i,j,N,M,t);
  else if(G[i][j].V[1].dj>G[i][j].V[0].dj)
  {G[i][j].V[1].dj=G[i][j].V[0].dj;
   gril(i,j,N,M,t);
  }
  t=2;
  if(G[i][j].V[3].p==false&&G[i][j].V[2].dj==-1)
  gril(i,j,N,M,t);
  else if(G[i][j].V[2].dj>G[i][j].V[0].dj)
  {G[i][j].V[2].dj=G[i][j].V[0].dj;
   gril(i,j,N,M,t);
  }
 }
 if(a==1)
 {//cout<<G[i][j].V[1].q<<" ";
  
  //cout<<G[i][j].V[1].q<<" ";
  if(i-1>=0&&j+1<M&&(G[i-1][j+1].V[2].dj==-1||G[i-1][j+1].V[2].dj>G[i][j].V[1].dj+1))
  {G[i-1][j+1].V[2].dj=G[i][j].V[1].dj+1;
   temp=i-1; te=j+1; t=2;
   gril(temp,te,N,M,t);
  }
  if(j+1<M&&(G[i][j+1].V[0].dj==-1||G[i][j+1].V[0].dj>G[i][j].V[1].dj+1))
  {G[i][j+1].V[0].dj=G[i][j].V[1].dj+1;
   temp=j+1;
   t=0;
   gril(i,temp,N,M,t);
  }
  if(j+1<M&&(G[i][j+1].V[2].dj==-1||G[i][j+1].V[2].dj>G[i][j].V[1].dj+1))
  if(G[i][j].V[1].p==false||G[i][j+1].V[3].p==false)
  {G[i][j+1].V[2].dj=G[i][j].V[1].dj+1;
   temp=j+1;
   t=2;
   gril(i,temp,N,M,t);
  }
  if(i-1>=0&&(G[i-1][j].V[3].dj==-1||G[i-1][j].V[3].dj>G[i][j].V[1].dj+1))
  {G[i-1][j].V[3].dj=G[i][j].V[1].dj+1;
   temp=i-1;
   t=3;
   gril(temp,j,N,M,t);
  }
  if(i-1>=0&&(G[i-1][j].V[2].dj==-1||G[i-1][j].V[2].dj>G[i][j].V[1].dj+1))
  if(G[i][j].V[0].p==false||G[i-1][j].V[2].p==false)
  {G[i-1][j].V[2].dj=G[i][j].V[1].dj+1;
   temp=i-1; t=2;
   gril(temp,j,N,M,t);
  }
  t=3;
  if(G[i][j].V[1].p==false&&G[i][j].V[3].dj==-1)
  gril(i,j,N,M,t);
  else if(G[i][j].V[3].dj>G[i][j].V[1].dj)
  {G[i][j].V[3].dj=G[i][j].V[1].dj;
   gril(i,j,N,M,t);
  }
  t=0;
  if(G[i][j].V[0].p==false&&G[i][j].V[0].dj==-1)
  gril(i,j,N,M,t);
  else if(G[i][j].V[0].dj>G[i][j].V[1].dj)
  {G[i][j].V[0].dj=G[i][j].V[1].dj;
   gril(i,j,N,M,t);
  }
 }
 if(a==2)
 {//cout<<G[i][j].V[2].q<<" ";  G[i][j].V[2].q=true;
  //cout<<G[i][j].V[2].q<<" ";
  if(i+1<N&&j-1>=0&&(G[i+1][j-1].V[1].dj==-1||G[i+1][j-1].V[1].dj>G[i][j].V[2].dj+1))
  {G[i+1][j-1].V[1].dj=G[i][j].V[2].dj+1;
   temp=i+1; te=j-1; t=1;
   gril(temp,te,N,M,t);
  }
  if(i+1<N&&(G[i+1][j].V[0].dj==-1||G[i+1][j].V[0].dj>G[i][j].V[2].dj+1))
  {G[i+1][j].V[0].dj=G[i][j].V[2].dj+1;
   temp=i+1; t=0;
   gril(temp,j,N,M,t);
  }
  if(i+1<N&&(G[i+1][j].V[1].dj==-1||G[i+1][j].V[1].dj>G[i][j].V[2].dj+1))
  if(G[i][j].V[2].p==false||G[i+1][j].V[0].p==false)
  {G[i+1][j].V[1].dj=G[i][j].V[2].dj+1;
   temp=i+1; t=1;
   gril(temp,j,N,M,t);
  }
  if(j-1>=0&&(G[i][j-1].V[3].dj==-1||G[i][j-1].V[3].dj>G[i][j].V[2].dj+1))
  {G[i][j-1].V[3].dj=G[i][j].V[2].dj+1;
   temp=j-1; t=3;
   gril(i,temp,N,M,t);
  }
  if(j-1>=0&&(G[i][j-1].V[1].dj==-1||G[i][j-1].V[1].dj>G[i][j].V[2].dj+1))
  if(G[i][j].V[3].p==false||G[i][j-1].V[1].p==false)
  {G[i][j-1].V[1].dj=G[i][j].V[2].dj+1;
   temp=j-1; t=1;
   gril(i,temp,N,M,t);
  }
  t=0;
  if(G[i][j].V[3].p==false&&G[i][j].V[0].dj==-1)
  gril(i,j,N,M,t);
  else if(G[i][j].V[0].dj>G[i][j].V[2].dj)
  {G[i][j].V[0].dj=G[i][j].V[2].dj;
   gril(i,j,N,M,t);
  }
  t=3;
  if(G[i][j].V[2].p==false&&G[i][j].V[3].dj==-1)
  gril(i,j,N,M,t);
  else if(G[i][j].V[3].dj>G[i][j].V[2].dj)
  {G[i][j].V[3].dj=G[i][j].V[2].dj;
   gril(i,j,N,M,t);
  }
 }
 if(a==3)
 {//cout<<G[i][j].V[3].q<<" ";
 
  //cout<<G[i][j].V[3].q<<" ";
  if(i+1<N&&j+1<M&&(G[i+1][j+1].V[0].dj==-1||G[i+1][j+1].V[0].dj>G[i][j].V[3].dj+1))
  {G[i+1][j+1].V[0].dj=G[i][j].V[3].dj+1;
   temp=i+1; te=j+1; t=0;
   gril(temp,te,N,M,t);
  }
  if(j+1<M&&(G[i][j+1].V[2].dj==-1||G[i][j+1].V[2].dj>G[i][j].V[3].dj+1))
  {G[i][j+1].V[2].dj=G[i][j].V[3].dj+1;
   temp=j+1; t=2;
   gril(i,temp,N,M,t);
  }
  if(j+1<M&&(G[i][j+1].V[0].dj==-1||G[i][j+1].V[0].dj>G[i][j].V[3].dj+1))
  if(G[i][j].V[1].p==false||G[i][j+1].V[3].p==false)
  {G[i][j+1].V[0].dj=G[i][j].V[3].dj+1;
   temp=j+1; t=0;
   gril(i,temp,N,M,t);
  }
  if(i+1<N&&(G[i+1][j].V[1].dj==-1||G[i+1][j].V[1].dj>G[i][j].V[3].dj+1))
  {G[i+1][j].V[1].dj=G[i][j].V[3].dj+1;
   temp=i+1; t=1;
   gril(temp,j,N,M,t);
  }
  if(i+1<N&&(G[i+1][j].V[0].dj==-1||G[i+1][j].V[0].dj>G[i][j].V[3].dj+1))
  if(G[i][j].V[2].p==false||G[i+1][j].V[0].p==false)
  {G[i+1][j].V[0].dj=G[i][j].V[3].dj+1;
   temp=i+1; t=0;
   gril(temp,j,N,M,t);
  }
  t=2;
  if(G[i][j].V[2].p==false&&G[i][j].V[2].dj==-1)
  gril(i,j,N,M,t);
  else if(G[i][j].V[2].dj>G[i][j].V[3].dj)
  {G[i][j].V[2].dj=G[i][j].V[3].dj;
   gril(i,j,N,M,t);
  }
  t=1;
  if(G[i][j].V[1].p==false&&G[i][j].V[1].dj==-1)
  gril(i,j,N,M,t);
  else if(G[i][j].V[1].dj>G[i][j].V[3].dj)
  {G[i][j].V[1].dj=G[i][j].V[3].dj;
   gril(i,j,N,M,t);
  }
 }
}

int cammina(int N,int M,int griglia[][1000])
{int i,j;
 for(i=0;i<N;i++)
 for(j=0;j<M;j++)
 {b2(griglia[i][j],g);
  if(g[0]==1)
  G[i][j].V[0].p=true;
  if(g[1]==1)
  G[i][j].V[1].p=true;
  if(g[2]==1)
  G[i][j].V[2].p=true;
  if(g[3]==1)
  G[i][j].V[3].p=true;
 }
 G[0][0].V[0].dj=1;
 G[0][0].V[1].dj=1;
 G[0][0].V[2].dj=1;
 G[0][0].V[3].dj=1;
 gril(0,0,N,M,0);
 //cout<<G[i][j].V[3].dj<<" ";
 return G[N+1][M+1].V[3].dj;
}
int main(){int i,j;
cin>>N;
cin>>M;
for(i=0;i<N;i++)
for(j=0;j<M;j++)
cin>>griglia[i][j];
G[N-1][M-1].V[3].dj=-1;
cout<<cammina(N,M,griglia);
system("PAUSE");
}

MrBrionix · 9 Agosto 2016, 6:50pm

Ho dato un’occhiata al codice e ho individuato 2 tipi di errori:

ERRORE 1
nella funzione gril, ogni volta che devi passare da una cella a un’altra senza cambiare piastrella hai scritto un codice di questo tipo:

if(G[i][j].V[0].p==false&&G[i][j].V[1].dj==-1)
  gril(i,j,N,M,t);
  else if(G[i][j].V[1].dj>G[i][j].V[0].dj)
  {G[i][j].V[1].dj=G[i][j].V[0].dj;
   gril(i,j,N,M,t);
  }

non capisco per quale motivo hai scritto che se la cella non è mai visitata richiami la fuzione gril ma lasci il suo valore originale(che è -1)
Ho corretto facendo in modo che aggiornando il suo valore:

if(G[i][j].V[3].p==false&&(G[i][j].V[3].dj==-1||G[i][j].V[3].dj>G[i][j].V[2].dj))
  {G[i][j].V[3].dj=G[i][j].V[2].dj;
   gril(i,j,N,M,t);
  }

ERRORE 2:
Prima di far partire la ricorsione tu scrivi:

G[0][0].V[0].dj=1;
 G[0][0].V[1].dj=1;
 G[0][0].V[2].dj=1;
 G[0][0].V[3].dj=1;

Ma non è sempre detto: se la piastrella iniziale ha, per esempio, velenosità 5 non è vero che G[0][0].V[1].dj=1; e G[0][0].V[3].dj=1;
L’unica sicurezza è che:

G[0][0].V[0].dj=1;

che è quella di partenza.

Dopo aver corretto questo errori, ho controllato se era corretta inviando la soluzione ma ho ottenuto un TLE nell’ultimo testcase.

Così ho rimosso alcuni controlli che erano superflui (come per esempio la sottocella 1 di una piastrella con la sottocella 2 della piastrella accanto, alla sottocella 2 della piastrella accanto ci si arriva lo stesso con la ricorsione e sempre con il numero di piastrelle minimo) e ho notato che con la ricorsione le piastrelle venivano considerate molte volte, così ho tolto la ricorsione e ho inserito un vector’<vector’ > lista a cui aggiungevo le nuove piastrelle da controllare (stile dijkstra) e in questo modo ho passato il testcase 8, però è comparso un TLE nel testcase 2.
Dato che nel testcase 2 il veleno non c’è, per risolverlo ho fatto in modo di controllare quando non c’è veleno e in quel caso stampo il numero massimo tra N e M, che è chiaramente la soluzione.
Ora passa tutti i testcase e fa 100/100.
Nel caso peggiore impiega 1,321 s.

Ecco il tuo codice corretto:

#include <fstream>
#include <cstdlib>
#include <vector>
using namespace std;
vector<vector<int> > lista;
struct vel{int dj;bool p;
           vel(): dj(-1),p(false){}
           };
struct gri{vel V[4];};
gri G[1000][1000]; 
int griglia[1000][1000];
int N,M;
int g[4];
void b2(int n,int V[])
{int c=0;
 while (n>0)
 {V[c]=n%2;
  n=n/2;
  c++;
 }
 while(c<4)
 {V[c]=0;
  c++;
 }
}
void gril(int i,int j,int a)
{int temp,te,t;
vector<int> z;
 if(a==0)
 {//cout<<G[i][j].V[0].q<<" ";
 
  //cout<<G[i][j].V[0].q<<" ";
  if(j-1>=0&&(G[i][j-1].V[1].dj==-1 || G[i][j-1].V[1].dj>G[i][j].V[0].dj+1))
  {G[i][j-1].V[1].dj=G[i][j].V[0].dj+1;
   //cout<<i<<j<<endl;
   temp=j-1;
   t=1;
   
   z.clear();
   z.push_back(i);
   z.push_back(temp);
   z.push_back(t);
   lista.push_back(z);
  }
  if(j-1>=0&&i-1>=0&&(G[i-1][j-1].V[3].dj==-1||G[i-1][j-1].V[3].dj>G[i][j].V[0].dj+1))
  {G[i-1][j-1].V[3].dj=G[i][j].V[0].dj+1;
   //cout<<G[i-1][j-1].V[3].dj<<endl;
   temp=i-1; te=j-1;
   t=3;
   z.clear();
   z.push_back(temp);
   z.push_back(te);
   z.push_back(t);
   lista.push_back(z);
  }
  if(i-1>=0&&(G[i-1][j].V[2].dj==-1||G[i-1][j].V[2].dj>G[i][j].V[0].dj+1))
  {G[i-1][j].V[2].dj=G[i][j].V[0].dj+1;
   //cout<<G[i-1][j].V[2].dj<<endl;
   temp=i-1; t=2;
   
   z.clear();
   z.push_back(temp);
   z.push_back(j);
   z.push_back(t);
   lista.push_back(z);
  }
  t=1;
  if(G[i][j].V[0].p==false&&(G[i][j].V[1].dj==-1||G[i][j].V[1].dj>G[i][j].V[0].dj))
  {G[i][j].V[1].dj=G[i][j].V[0].dj;
   
   z.clear();
   z.push_back(i);
   z.push_back(j);
   z.push_back(t);
   lista.push_back(z);
  }
  t=2;
  if(G[i][j].V[2].p==false&&(G[i][j].V[2].dj==-1||G[i][j].V[2].dj>G[i][j].V[0].dj))
  {G[i][j].V[2].dj=G[i][j].V[0].dj;
   
   z.clear();
   z.push_back(i);
   z.push_back(j);
   z.push_back(t);
   lista.push_back(z);
  }
 }
 if(a==1)
 {//cout<<G[i][j].V[1].q<<" ";
  
  //cout<<G[i][j].V[1].q<<" ";
  if(i-1>=0&&j+1<M&&(G[i-1][j+1].V[2].dj==-1||G[i-1][j+1].V[2].dj>G[i][j].V[1].dj+1))
  {G[i-1][j+1].V[2].dj=G[i][j].V[1].dj+1;
   temp=i-1; te=j+1; t=2;
   
   z.clear();
   z.push_back(temp);
   z.push_back(te);
   z.push_back(t);
   lista.push_back(z);
  }
  if(j+1<M&&(G[i][j+1].V[0].dj==-1||G[i][j+1].V[0].dj>G[i][j].V[1].dj+1))
  {G[i][j+1].V[0].dj=G[i][j].V[1].dj+1;
   temp=j+1;
   t=0;
   
   z.clear();
   z.push_back(i);
   z.push_back(temp);
   z.push_back(t);
   lista.push_back(z);
  }
  if(i-1>=0&&(G[i-1][j].V[3].dj==-1||G[i-1][j].V[3].dj>G[i][j].V[1].dj+1))
  {G[i-1][j].V[3].dj=G[i][j].V[1].dj+1;
   temp=i-1;
   t=3;
   z.clear();
   z.push_back(temp);
   z.push_back(j);
   z.push_back(t);
   lista.push_back(z);
  }
  t=3;
  if(G[i][j].V[1].p==false&&(G[i][j].V[3].dj==-1||G[i][j].V[3].dj>G[i][j].V[1].dj))
  {G[i][j].V[3].dj=G[i][j].V[1].dj;
   
   z.clear();
   z.push_back(i);
   z.push_back(j);
   z.push_back(t);
   lista.push_back(z);
  }
  t=0;
  if(G[i][j].V[0].p==false&&(G[i][j].V[0].dj==-1||G[i][j].V[0].dj>G[i][j].V[1].dj))
  {G[i][j].V[0].dj=G[i][j].V[1].dj;
   
   z.clear();
   z.push_back(i);
   z.push_back(j);
   z.push_back(t);
   lista.push_back(z);
  }
 }
 if(a==2)
 {//cout<<G[i][j].V[2].q<<" ";  G[i][j].V[2].q=true;
  //cout<<G[i][j].V[2].q<<" ";
  if(i+1<N&&j-1>=0&&(G[i+1][j-1].V[1].dj==-1||G[i+1][j-1].V[1].dj>G[i][j].V[2].dj+1))
  {G[i+1][j-1].V[1].dj=G[i][j].V[2].dj+1;
   temp=i+1; te=j-1; t=1;
   z.clear();
   z.push_back(temp);
   z.push_back(te);
   z.push_back(t);
   lista.push_back(z);
  }
  if(i+1<N&&(G[i+1][j].V[0].dj==-1||G[i+1][j].V[0].dj>G[i][j].V[2].dj+1))
  {G[i+1][j].V[0].dj=G[i][j].V[2].dj+1;
   temp=i+1; t=0;
   
   z.clear();
   z.push_back(temp);
   z.push_back(j);
   z.push_back(t);
   lista.push_back(z);
  }
  if(j-1>=0&&(G[i][j-1].V[3].dj==-1||G[i][j-1].V[3].dj>G[i][j].V[2].dj+1))
  {G[i][j-1].V[3].dj=G[i][j].V[2].dj+1;
   temp=j-1; t=3;
   z.clear();
   z.push_back(i);
   z.push_back(temp);
   z.push_back(t);
   lista.push_back(z);
  }
  t=0;
  if(G[i][j].V[2].p==false&&(G[i][j].V[0].dj==-1||G[i][j].V[0].dj>G[i][j].V[2].dj))
  {G[i][j].V[0].dj=G[i][j].V[2].dj;
   z.clear();
   z.push_back(i);
   z.push_back(j);
   z.push_back(t);
   lista.push_back(z);
  }
  t=3;
  if(G[i][j].V[3].p==false&&(G[i][j].V[3].dj==-1||G[i][j].V[3].dj>G[i][j].V[2].dj))
  {G[i][j].V[3].dj=G[i][j].V[2].dj;
   z.clear();
   z.push_back(i);
   z.push_back(j);
   z.push_back(t);
   lista.push_back(z);
  }
 }
 if(a==3)
 {//cout<<G[i][j].V[3].q<<" ";
 
  //cout<<G[i][j].V[3].q<<" ";
  if(i+1<N&&j+1<M&&(G[i+1][j+1].V[0].dj==-1||G[i+1][j+1].V[0].dj>G[i][j].V[3].dj+1))
  {G[i+1][j+1].V[0].dj=G[i][j].V[3].dj+1;
   temp=i+1; te=j+1; t=0;
   z.clear();
   z.push_back(temp);
   z.push_back(te);
   z.push_back(t);
   lista.push_back(z);
  }
  if(j+1<M&&(G[i][j+1].V[2].dj==-1||G[i][j+1].V[2].dj>G[i][j].V[3].dj+1))
  {G[i][j+1].V[2].dj=G[i][j].V[3].dj+1;
   temp=j+1; t=2;
   z.clear();
   z.push_back(i);
   z.push_back(temp);
   z.push_back(t);
   lista.push_back(z);
  }
  if(i+1<N&&(G[i+1][j].V[1].dj==-1||G[i+1][j].V[1].dj>G[i][j].V[3].dj+1))
  {G[i+1][j].V[1].dj=G[i][j].V[3].dj+1;
   temp=i+1; t=1;
   z.clear();
   z.push_back(temp);
   z.push_back(j);
   z.push_back(t);
   lista.push_back(z);
  }
  t=2;
  if(G[i][j].V[3].p==false&&(G[i][j].V[2].dj==-1||G[i][j].V[2].dj>G[i][j].V[3].dj))
  {G[i][j].V[2].dj=G[i][j].V[3].dj;
   
   z.clear();
   z.push_back(i);
   z.push_back(j);
   z.push_back(t);
   lista.push_back(z);
  }
  t=1;
  if(G[i][j].V[1].p==false&&(G[i][j].V[1].dj==-1||G[i][j].V[1].dj>G[i][j].V[3].dj))
  {G[i][j].V[1].dj=G[i][j].V[3].dj;
   z.clear();
   z.push_back(i);
   z.push_back(j);
   z.push_back(t);
   lista.push_back(z);
  }
 }
}

int cammina(int N,int M,int griglia[][1000])
{int i,j;
 for(i=0;i<N;i++)
 for(j=0;j<M;j++)
 {b2(griglia[i][j],g);
  if(g[0]==1)
  G[i][j].V[0].p=true;
  if(g[1]==1)
  G[i][j].V[1].p=true;
  if(g[2]==1)
  G[i][j].V[3].p=true;
  if(g[3]==1)
  G[i][j].V[2].p=true;
 }
 G[0][0].V[0].dj=1;
 
 vector<int> inizio;
 inizio.clear();
   inizio.push_back(0);
   inizio.push_back(0);
   inizio.push_back(0);
   lista.push_back(inizio);
   int cont=0;
   while(cont<lista.size()){
   	gril(lista[cont][0],lista[cont][1],lista[cont][2]);
   	cont++;
   }
   
 //cout<<G[i][j].V[3].dj<<" ";
 return G[N-1][M-1].V[3].dj;
}
int main(){int i,j;
ifstream cin("input.txt");
ofstream cout("output.txt");
bool case2=true;
cin>>N;
cin>>M;
for(i=0;i<N;i++)
for(j=0;j<M;j++){
cin>>griglia[i][j];
if(griglia[i][j]!=0){
	case2=false;
}
}
if(case2){
	cout<<max(N,M)<<endl;
}
else
cout<<cammina(N,M,griglia)<<endl;
return 0;
}

sudden · 9 Agosto 2016, 7:47pm

Ci avevo anche pensato ad impostarlo come dijkistra, infatti la variabile dj dovrebbe ricordarne il nome

Sono proprio sbadato. Avevo notato,outtando dj per l’intera griglia finale,valori un po’ sospetti,come dei valori 0 che non dovrebbero essere previsti.Evidentemente sono venuti fuori da un -1 + 1.

Sinceramente mi aspettavo che fosse un codice da buttare, mi stavo già disperando per il tempo perso a scrivere un codice lunghissimo. Comincio a volerti bene, sei il mio salvatore

Grazie mille, anche questa volta

(Mi scuso ancora una volta per aver dato un grattacapo a wil che ha dovuto separare il codice dal messaggio principale al posto mio. Come si fa?)

MrBrionix · 9 Agosto 2016, 7:54pm

Prova a quotare il mio messaggio e controlla, non ho idea di come scriverlo facendo in modo che si veda

wil93 · 9 Agosto 2016, 11:41pm

No problem comunque basta usare il tasto “testo preformattato” nell’editor, ovvero il tasto </>, oppure semplicemente ti basta anteporre 4 spazi prima di ogni riga.

Per un tutorial completo Markdown Reference

v.bizzarri · 22 Luglio 2018, 12:56am

Domanda:
Le piastrelle con velenosità 1 o 2 o 4 o 8 non sono trattabili come quelle a velenosità 0?
A me sembra di si, anche in quelle si può entrare da dove si vuole ed uscire dove si vuole.