API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Dec 11th, 2017
75
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.84 KB | None | 0 0
raw download clone embed print report
  1.  
  2. Tupla<TipoRetorno, Iterador<Iterador<Tupla<int, int>>>> Sistema::CaminoCaballo(Tupla<int, int>& salida, Tupla<int, int>& destino, nat cantAPasar, nat tamTablero, Iterador<Tupla<int, int>>& pasar, Iterador<Tupla<int, int>>& noPasar) {
  3. Tupla<int, int> actual = salida;
  4. nat pasosOptimos = 99999999999999;
  5. nat pos = 0;
  6. Array<Tupla<int, int>> lista(tamTablero);
  7. Puntero<Lista<Array<Tupla<int, int>>>> solucion = new ListaImp<Array<Tupla<int, int>>>(Comparador<Array<Tupla<int, int>>>::Default);
  8. Tupla<int, int> aux = Tupla<int, int>(salida.Dato1, salida.Dato2);
  9. lista[0] = aux;
  10. CaminoCaballoBT(0, 1, salida, destino, cantAPasar, tamTablero, pasar, noPasar, 0, pasosOptimos, lista, solucion);
  11. nat cont = solucion->Largo() - 1;
  12. Array<Iterador<Tupla<int,int>>> ret(solucion->Largo());
  13. while (!solucion->EstaVacia()) {
  14. ret[cont] = solucion->Cabeza().ObtenerIterador();
  15. solucion->EliminarCabeza();
  16. cont--;
  17. }
  18. Tupla<TipoRetorno, Iterador<Iterador<Tupla<int,int>>>> retorno = Tupla<TipoRetorno, Iterador<Iterador<Tupla<int,int>>>>(OK, ret.ObtenerIterador());
  19. return retorno;
  20. }
  21. void Sistema::CaminoCaballoBT(nat cantPasar, nat pos, Tupla<int, int>& salida, Tupla<int, int>& destino, nat cantAPasar, nat tamTablero, Iterador<Tupla<int, int>>& pasar, Iterador<Tupla<int, int>>& noPasar, nat cantidadPasos, nat &pasosOptimo, Array<Tupla<int, int>> lista, Puntero<Lista<Array<Tupla<int, int>>>> &solucion){
  22. if (cantidadPasos > pasosOptimo)return;
  23. if (cantPasar >= cantAPasar && salida == destino && cantidadPasos < pasosOptimo) {
  24. nat posAux = 0;
  25. solucion->Vaciar();
  26. Array<Tupla<int, int>> sol(pos);
  27. while (posAux < pos) {
  28. sol[posAux] = lista[posAux];
  29. posAux++;
  30. }
  31. solucion->Insertar(sol);
  32. pasosOptimo = cantidadPasos;
  33. return;
  34. }
  35. if (cantPasar >= cantAPasar && salida == destino && cantidadPasos == pasosOptimo) {
  36. nat posAux = 0;
  37. Array<Tupla<int, int>> sol(pos);
  38. while (posAux < pos) {
  39. sol[posAux] = lista[posAux];
  40. posAux++;
  41. }
  42. solucion->Insertar(sol);
  43. return;
  44. }
  45. if ((salida.Dato1 > 1) && (salida.Dato2 > 0)) {
  46. Tupla<int, int> aux = Tupla<int, int>(salida.Dato1 - 2, salida.Dato2 - 1);
  47. if (pos <= 1 || lista[pos - 2] != aux) {
  48. if (PerteneceIteradorTupla(pasar, Tupla<int, int>(salida.Dato1 - 2, salida.Dato2 - 1))) {
  49. lista[pos] = aux;
  50. CaminoCaballoBT(cantPasar + 1, pos + 1, aux, destino, cantAPasar, tamTablero, pasar, noPasar, cantidadPasos + 1, pasosOptimo, lista, solucion);
  51. }
  52. else if (!PerteneceIteradorTupla(noPasar, Tupla<int, int>(salida.Dato1 - 2, salida.Dato2 - 1))) {
  53. lista[pos] = aux;
  54. CaminoCaballoBT(cantPasar, pos + 1, aux, destino, cantAPasar, tamTablero, pasar, noPasar, cantidadPasos + 1, pasosOptimo, lista, solucion);
  55. }
  56. }
  57. }
  58. if ((salida.Dato1 > 0) && (salida.Dato2 > 1)) {
  59. Tupla<int, int> aux = Tupla<int, int>(salida.Dato1 - 1, salida.Dato2 - 2);
  60. if (pos <= 1 || lista[pos - 2] != aux) {
  61. if (PerteneceIteradorTupla(pasar, Tupla<int, int>(salida.Dato1 - 1, salida.Dato2 - 2))) {
  62. lista[pos] = aux;
  63. CaminoCaballoBT(cantPasar + 1, pos + 1, aux, destino, cantAPasar, tamTablero, pasar, noPasar, cantidadPasos + 1, pasosOptimo, lista, solucion);
  64. }
  65. else if (!PerteneceIteradorTupla(noPasar, Tupla<int, int>(salida.Dato1 - 1, salida.Dato2 - 2))) {
  66. lista[pos] = aux;
  67. CaminoCaballoBT(cantPasar, pos + 1, aux, destino, cantAPasar, tamTablero, pasar, noPasar, cantidadPasos + 1, pasosOptimo, lista, solucion);
  68. }
  69. }
  70. }
  71. if ((salida.Dato1 > 1) && (salida.Dato2 + 1 < (int)tamTablero)) {
  72. Tupla<int, int> aux = Tupla<int, int>(salida.Dato1 - 2, salida.Dato2 + 1);
  73. if (pos <= 1 || lista[pos - 2] != aux) {
  74. if (PerteneceIteradorTupla(pasar, Tupla<int, int>(salida.Dato1 - 2, salida.Dato2 + 1))) {
  75. lista[pos] = aux;
  76. CaminoCaballoBT(cantPasar + 1, pos + 1, aux, destino, cantAPasar, tamTablero, pasar, noPasar, cantidadPasos + 1, pasosOptimo, lista, solucion);
  77. }
  78. else if (!PerteneceIteradorTupla(noPasar, Tupla<int, int>(salida.Dato1 - 2, salida.Dato2 + 1))) {
  79. lista[pos] = aux;
  80. CaminoCaballoBT(cantPasar, pos + 1, aux, destino, cantAPasar, tamTablero, pasar, noPasar, cantidadPasos + 1, pasosOptimo, lista, solucion);
  81. }
  82. }
  83. }
  84. if ((salida.Dato1 > 0) && (salida.Dato2 + 2 < (int)tamTablero)) {
  85. Tupla<int, int> aux = Tupla<int, int>(salida.Dato1 - 1, salida.Dato2 + 2);
  86. if (pos <= 1 || lista[pos - 2] != aux) {
  87. if (PerteneceIteradorTupla(pasar, Tupla<int, int>(salida.Dato1 - 1, salida.Dato2 + 2))) {
  88. lista[pos] = aux;
  89. CaminoCaballoBT(cantPasar + 1, pos + 1, aux, destino, cantAPasar, tamTablero, pasar, noPasar, cantidadPasos + 1, pasosOptimo, lista, solucion);
  90. }
  91. else if (!PerteneceIteradorTupla(noPasar, Tupla<int, int>(salida.Dato1 - 1, salida.Dato2 + 2))) {
  92. lista[pos] = aux;
  93. CaminoCaballoBT(cantPasar, pos + 1, aux, destino, cantAPasar, tamTablero, pasar, noPasar, cantidadPasos + 1, pasosOptimo, lista, solucion);
  94. }
  95. }
  96. }
  97. if ((salida.Dato1 + 1 < (int)tamTablero) && (salida.Dato2 + 2 < (int)tamTablero)) {
  98. Tupla<int, int> aux = Tupla<int, int>(salida.Dato1 + 1, salida.Dato2 + 2);
  99. if (pos <= 1 || lista[pos - 2] != aux) {
  100. if (PerteneceIteradorTupla(pasar, Tupla<int, int>(salida.Dato1 + 1, salida.Dato2 + 2))) {
  101. lista[pos] = aux;
  102. CaminoCaballoBT(cantPasar + 1, pos + 1, aux, destino, cantAPasar, tamTablero, pasar, noPasar, cantidadPasos + 1, pasosOptimo, lista, solucion);
  103. }
  104. else if (!PerteneceIteradorTupla(noPasar, Tupla<int, int>(salida.Dato1 + 1, salida.Dato2 + 2))) {
  105. lista[pos] = aux;
  106. CaminoCaballoBT(cantPasar, pos + 1, aux, destino, cantAPasar, tamTablero, pasar, noPasar, cantidadPasos + 1, pasosOptimo, lista, solucion);
  107. }
  108. }
  109. }
  110. if ((salida.Dato1 + 2 < (int)tamTablero) && (salida.Dato2 + 1 < (int)tamTablero)) {
  111. Tupla<int, int> aux = Tupla<int, int>(salida.Dato1 + 2, salida.Dato2 + 1);
  112. if (pos <= 1 || lista[pos - 2] != aux) {
  113. if (PerteneceIteradorTupla(pasar, Tupla<int, int>(salida.Dato1 + 2, salida.Dato2 + 1))) {
  114. lista[pos] = aux;
  115. CaminoCaballoBT(cantPasar + 1, pos + 1, aux, destino, cantAPasar, tamTablero, pasar, noPasar, cantidadPasos + 1, pasosOptimo, lista, solucion);
  116. }
  117. else if (!PerteneceIteradorTupla(noPasar, Tupla<int, int>(salida.Dato1 + 2, salida.Dato2 + 1))) {
  118. lista[pos] = aux;
  119. CaminoCaballoBT(cantPasar, pos + 1, aux, destino, cantAPasar, tamTablero, pasar, noPasar, cantidadPasos + 1, pasosOptimo, lista, solucion);
  120. }
  121. }
  122. }
  123. if ((salida.Dato1 + 2 < (int)tamTablero) && (salida.Dato2 > 0)) {
  124. Tupla<int, int> aux = Tupla<int, int>(salida.Dato1 + 2, salida.Dato2 - 1);
  125. if (pos <= 1 || lista[pos - 2] != aux) {
  126. if (PerteneceIteradorTupla(pasar, Tupla<int, int>(salida.Dato1 + 2, salida.Dato2 - 1))) {
  127. lista[pos] = aux;
  128. CaminoCaballoBT(cantPasar + 1, pos + 1, aux, destino, cantAPasar, tamTablero, pasar, noPasar, cantidadPasos + 1, pasosOptimo, lista, solucion);
  129. }
  130. else if (!PerteneceIteradorTupla(noPasar, Tupla<int, int>(salida.Dato1 + 2, salida.Dato2 - 1))) {
  131. lista[pos] = aux;
  132. CaminoCaballoBT(cantPasar, pos + 1, aux, destino, cantAPasar, tamTablero, pasar, noPasar, cantidadPasos + 1, pasosOptimo, lista, solucion);
  133. }
  134. }
  135. }
  136. if ((salida.Dato1 + 1 < (int)tamTablero) && (salida.Dato2 > 1)) {
  137. Tupla<int, int> aux = Tupla<int, int>(salida.Dato1 + 1, salida.Dato2 - 2);
  138. if (pos <= 1 || lista[pos - 2] != aux) {
  139. if (PerteneceIteradorTupla(pasar, Tupla<int, int>(salida.Dato1 + 1, salida.Dato2 - 2))) {
  140. lista[pos] = aux;
  141. CaminoCaballoBT(cantPasar + 1, pos + 1, aux, destino, cantAPasar, tamTablero, pasar, noPasar, cantidadPasos + 1, pasosOptimo, lista, solucion);
  142. }
  143. else if (!PerteneceIteradorTupla(noPasar, Tupla<int, int>(salida.Dato1 + 1, salida.Dato2 - 2))) {
  144. lista[pos] = aux;
  145. CaminoCaballoBT(cantPasar, pos + 1, aux, destino, cantAPasar, tamTablero, pasar, noPasar, cantidadPasos + 1, pasosOptimo, lista, solucion);
  146. }
  147. }
  148. }
  149. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!