SHARE
TWEET

Backtracking_caballo

a guest Apr 23rd, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <iomanip>
  3.  
  4. using namespace std;
  5.  
  6. const int N = 30;
  7.  
  8. bool comprobar(int matriz[][N], const int n){
  9.     bool encontrado = true;
  10.     for(int i = 0; i<n; i++){
  11.         for(int j = 0; j<n; j++){
  12.             if(matriz[i][j]<=0){
  13.                 encontrado = false;
  14.             }
  15.         }
  16.     }
  17.     return encontrado;
  18. }
  19.  
  20. void mostrarTabla(int matriz[][N], const int n){
  21.     for(int i = 0; i<n; i++){
  22.         for(int j = 0; j<n; j++){
  23.             cout << setw(4) << matriz[i][j];
  24.         }
  25.         cout << endl;
  26.         cout << endl;
  27.     }
  28.     cout << endl;
  29.     cout << "---------------------------------------" << endl;
  30.     cout << endl;
  31. }
  32.  
  33.  
  34. bool comprPos(const int matriz[][N], const int fila, const int columna, const int n){
  35.         return (fila<n)&&(fila>=0)&&(columna<n)&&(columna>=0)&&(matriz[fila][columna]==0);
  36. }
  37.  
  38. void caballo(int matriz[][N], bool& encontrado, int fila, int columna, int i, const int n){
  39.     matriz[fila][columna] = i;
  40.     //mostrarTabla(matriz, n);
  41.     encontrado = comprobar(matriz,n);
  42.     if(!encontrado){
  43.         if(comprPos(matriz, fila-1,columna+2,n)){//1
  44.             caballo(matriz, encontrado, fila-1, columna+2, i+1, n);
  45.         }
  46.         if(comprPos(matriz, fila-2, columna+1, n) && !encontrado){//2
  47.             caballo(matriz, encontrado, fila-2, columna+1, i+1, n);
  48.         }
  49.         if(comprPos(matriz, fila-2, columna-1, n) && !encontrado){//3
  50.             caballo(matriz, encontrado, fila-2, columna-1, i+1, n);
  51.         }
  52.         if(comprPos(matriz, fila-1, columna-2, n) && !encontrado){//4
  53.             caballo(matriz, encontrado, fila-1, columna-2, i+1, n);
  54.         }
  55.         if(comprPos(matriz, fila+1, columna-2, n) && !encontrado){//5
  56.             caballo(matriz, encontrado, fila+1, columna-2, i+1, n);
  57.         }
  58.         if(comprPos(matriz, fila+2, columna-1, n) && !encontrado){//6
  59.             caballo(matriz, encontrado, fila+2, columna-1, i+1, n);
  60.         }
  61.         if(comprPos(matriz, fila+2, columna+1, n) && !encontrado){//7
  62.             caballo(matriz, encontrado, fila+2, columna+1, i+1, n);
  63.         }
  64.         if(comprPos(matriz, fila+1, columna+2, n) && !encontrado){//8
  65.             caballo(matriz, encontrado, fila+1, columna+2, i+1, n);
  66.         }
  67.     }
  68.     if(!encontrado){
  69.         matriz[fila][columna]=0;
  70.     }
  71. }
  72.  
  73. int main(){
  74.     int n;
  75.     cout << "Introduce el numero de filas y columnas: "  << flush;
  76.     cin >> n;
  77.     cout << endl << endl;
  78.  
  79.     int matriz[N][N] = {{0}};
  80.     bool encontrado = false;
  81.     caballo(matriz, encontrado, 0, 0, 1, n);
  82.  
  83.     if(encontrado){
  84.         mostrarTabla(matriz,n);
  85.     }
  86.     else{
  87.         cout << "Me he perdido ajjaj" << endl;
  88.     }
  89.  
  90.     return 0;
  91. }
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