Es a tempo 5

#include<iostream>
using namespace std;

//PRE=(N ha almeno m*m elementi definiti,  0<=i<m, j è definito e P ha m-i posizioni)

bool trova(bool* N, int m, int i, int j, int*P){
    if(N[i * m + j] != 1){
        return false;
    }else if(N[i * m + j] && i == 4){
        P[i] = j;
        return true;
    }else{
        P[i] = j;
        if(i == 0){
            return trova(N, m, i + 1, j, P) || trova(N, m, i + 1, j + 1, P);
        }else if(i == 4){
            return trova(N, m, i + 1, j - 1, P) || trova(N, m, i + 1, j, P);
        }else{
            return trova(N, m, i + 1, j - 1, P) || trova(N, m, i + 1, j, P) || trova(N, m, i + 1, j + 1, P);
        }
    }
}

//POST_t=(restituisce true sse in N vista come X[m][m] c’è un cammino dalla casella(i,j) alla riga m-1 composto da sole caselle bianche)&&(se la risposta è true,in P [0..m-i-1] c’è il cammino più a sinistra con queste proprietà)

/*

    Caso base 1:
        La casella esaminata contiene un valore diverso da 1: in tal caso non sono in un percorso valido, perciò è corretto ritornare false
    Caso base 2:
        La casella esaminata contiene il valore 1 e si trova nell'ultima riga (riga m): in tal caso, dopo aver salvato la posizione,
        è corretto restituire true in quanto esiste un percorso valido per arrivare all'ultima riga

    A questo punto salvo la posizione di N in cui mi trovo e si presentano 3 casi:
    Caso 1:
        Se i == 0:
            In tal caso per rispettare la PRE si devono controllare soltanto le celle sotto o a sinistra di quella corrente in quanto quella a
            destra avrebbe un indice negativo
    Caso 2:
        Se i == 4
            Con un ragionamento analogo a quello descritto per i == 0 si capisce che bisogna controllare soltanto gli elementi sotto e a destra della
            cella corrente in quanto quella a sinistra avrebbe un indice oltre m
    Caso 3:
        Se 0 < i < 4:
            In questo caso vanno controllate sia la cella direttamente sotto che quella sotto a sinistra che quella sotto a destra in quanto
            potrebbero formare un percorso valido e non sforano il limite imposto da m

    Così facendo so che il parametro i rispetta la PRE della funzione.
    Le variabili P, n e j sono parametri sempre definiti, in quanto o vengono passati dalla funzione partenza (all'interno della quale sono definiti)
    o dalla funzione trova stessa. La funzione trova non modifica mai N, quindi questo parametro sarà sempre definito. P viene modificato tuttavia
    solo i valori sono modificati, quindi la variabile è sempre definita. Infine j è un intero a cui viene sommato 1, il che porta a dire che
    il parametro j è sempre definito. Infine so che N ha almeno m * m elementi definiti in quanto viene preso come parametro che rispetta tale condizione
    quando la prima volta che la funzione trova viene chiamata e poi non viene mai modificato.

    Quindi posso dire che la PRE viene rispettata. Posso quindi fare il passo induttivo e supporre che la POST sia rispettata.

    Visto che la POST viene rispettata posso dire che se la funzione restituisce false non esiste un percorso valido, se invece restituisce true
    esiste un percorso valido dalla casella su cui è richiamata ad una dell'ultima riga. Inoltre so di per certo che se esiste un percorso da una
    cella che contiene 1 alla fine e che dalla cella in cui mi trovo alla cella da cui conosco il percorso per la fine allora esiste anche un
    percorso dalla cella in cui mi trovo alla fine.
    Inoltre se il percorso contenuto in P è il più a sinistra dalla cella esaminata fino alla fine allora anche dalla cella in cui mi trovo
    il percorso sarà quello più a sinistra

*/

//PRE_p=(N ha m*m valori definiti, 0<=k<=m e P ha m elementi)
bool partenza(bool* N, int m, int k, int* P){
    if(trova(N, m, 0, k, P)){
        return true;
    }else{
        if(k < m){
            return partenza(N, m, k + 1, P);
        }else{
            return false;
        }
    }
}
//POST_p=(risponde true sse esiste un cammino di caselle bianche dalla prima all’ultima riga di N, vista come X[m][m], e che inizia in una casella tra i e m-1 della prima riga di X)&&(se risponde true allora P[0..m-1] è il cammino più a sinistra con queste proprietà)

/*

    Caso base 1:
        La funzione trova resituisce true, quindi esiste un percorso che porta all'ultima riga: in tal caso è corretto restituire true;
    Caso base 2:
        La funzione trova restituisce false, quindi non esiste un percorso che porta all'ultima riga & k(colonna corrente) == m (ultima colonna):
        in tal caso ho esaminato tutte le possibili partenze e non ho trovato percorsi validi quindi è corretto restituire true

    A questo punto suppondo che la funzione trova restituisca false e che k < m:
        Siccome N contiene m * m elementi definiti (viene passato dal main, nel quale viene definito in modo da rispettare tale condizione e mai modificato),
        P ha m elementi (viene passato dal main, in cui viene definito in modo da rispettare tale condizione e non viene mai modificata la sua dimensione).
        A questo punto bisogna discutere i possibili valori di k e vedere se rispettano la PRE. si ha che k >= 0 in quanto viene passato
        come parametro uguale a 0 e poi non viene mai aumentato. Inoltre k <= m in quanto se k == m si rientra nel caso base sia che trova ritorni
        true sia che trova ritorni false.
        Visto che la PRE viene rispettata posso compiere il passo induttivo e supporre che la POST sia rispettata.

        Ci sono a questo punto 2 casi:
            1 - se partenza ritorna true esiste un percorso tale che parta dalla cella esaminata e arrivi alla fine della matrice
            2 - se partenza ritorna false esamino la cella di partenza successiva (se esiste). Se questa ritorna true allora il percorso esiste,
                altrimenti ripeto il passo 2.

        Se ho esaminato tutte le possibili partenze e la funzione ha sempre ritornato false allora il percorso non esiste.
        Inoltre P contiene il percorso più a sinistra come dimostrato dalla POST della funzione trova e dal fatto che l'array no nvenga modificato
        nella funzione partenza-


*/

void stampa(int*P,int m,int i)
{
  if(i==m)
    {cout<<endl; return;}
  cout<<'('<<i<<','<<P[i]<<')'<<' ';
  stampa(P,m,i+1);
}

int main()
{
  int m;
  cin>>m;
  int*P=new int[m];
  bool*N =new bool[m*m];
  for(int i=0; i<m*m; i++)
          cin>>N[i];
  bool x=partenza(N,m,0,P);//da fare
  cout<<"start"<<endl;
  if(x)
    { cout<<"esiste un cammino e quello più a sinistra è:"<<endl;
      stampa(P,m,0);

    }
  else
    cout<<"il cammino non esiste"<<endl;
  cout<<"end"<<endl;
   return 0;
}