SHARE
TWEET

Untitled

a guest Apr 18th, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. // PRE_p=(N ha m*m valori definiti, 0<=i<=m e P ha m elementi)
  5. bool partenza(bool *N, int m, int i, int *P);
  6. /* POST_p=(risponde true sse esiste un cammino di caselle bianche dalla prima all’ultima riga di N,
  7.  vista come X[m][m], e che inizia in una casellatra i e m-1 della prima riga di X)
  8.  &&(se risponde trueallora P[0..m-1] è il cammino più a sinistra con queste proprietà)
  9.  */
  10.  
  11. // PRE_t=(N ha almeno m*m elementi definiti,  0<=i<m, j è definitoe P ha m-i posizioni)
  12. bool trova(bool *N, int m, int i, int j, int *P);
  13. /* 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)
  14. &&(se la risposta è true,in P [0..m-i-1] c’è il cammino più a sinistra con queste proprietà)*/
  15.  
  16. void stampa(int *P, int m, int i)
  17. {
  18.   if (i == m)
  19.   {
  20.     cout << endl;
  21.     return;
  22.   }
  23.   cout << '(' << i << ',' << P[i] << ')' << ' ';
  24.   stampa(P, m, i + 1);
  25. }
  26.  
  27. main()
  28. {
  29.   int m;
  30.   cin >> m;
  31.   int *P = new int[m];
  32.   bool *N = new bool[m * m];
  33.   for (int i = 0; i < m * m; i++)
  34.     cin >> N[i];
  35.   bool x = partenza(N, m, 0, P); //da fare
  36.   cout << "start" << endl;
  37.   if (x)
  38.   {
  39.     cout << "esiste un cammino e quello più a sinistra è:" << endl;
  40.     stampa(P, m, 0);
  41.   }
  42.   else
  43.     cout << "il cammino non esiste" << endl;
  44.   cout << "end" << endl;
  45. }
  46. bool partenza(bool *N, int m, int i, int *P)
  47. {
  48.   if (trova(N, m, 0, i, P))
  49.   {
  50.     return true;
  51.   }
  52.   else if (i == m - 1 && !trova(N, m, 0, i, P))
  53.   {
  54.     return false;
  55.   }
  56.  
  57.   return partenza(N, m, i + 1, P);
  58. }
  59.  
  60. bool trova(bool *N, int m, int i, int j, int *P)
  61. {
  62.   if (*(N + (i * m) + j))
  63.   {
  64.     P[i] = j;
  65.   }
  66.   else
  67.   {
  68.     return false;
  69.   }
  70.   if (i == (m - 1)) // controllo che conclude la ricorsione
  71.   {
  72.     return true;
  73.   }
  74.  
  75.   return trova(N, m, i + 1, j - 1, P) || trova(N, m, i + 1, j, P) || trova(N, m, i + 1, j + 1, P);
  76. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top