Advertisement
Guest User

Untitled

a guest
Apr 24th, 2019
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.04 KB | None | 0 0
  1. // bludisko.cpp : This file contains the 'main' function. Program execution begins and ends there.
  2. //
  3. /*
  4. Mate k dispozicii bludisko definovane v stvorcekovej sieti takto:
  5. -steny labyrintu su zapisane znakom *;
  6. -medzery vyjadruju policka, cez ktore sa da prechadzat;
  7. -znak + oznacuje startovaciu poziciu hraca.
  8. Napiste program, ktory pomocou backtrackingu najde v tomto labyrinte najdlhsiu cestu.
  9. Hrac zacina v startovacom policku a na ziadne policko nevstupi viackrat.
  10. Skoncit s cestou moze na hociktorom policku.
  11. Program vypise riesenie do textovej plochy, pricom policka, cez ktore prejde, vypise ako znak '.'
  12. */
  13.  
  14. #include "pch.h"
  15. #include <iostream>
  16.  
  17. using namespace std;
  18.  
  19. int m = 8, n = 13; // rozmery bludiska
  20. // bludisko
  21.  
  22. char bludisko[8][13] = {
  23. {'*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*'},
  24. {'*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '*'},
  25. {'*', ' ', '*', '*', '*', '*', ' ', '*', '*', '*', '*', ' ', '*'},
  26. {'*', ' ', '*', ' ', ' ', '*', ' ', ' ', ' ', ' ', '*', ' ', '*'},
  27. {'*', ' ', ' ', '+', ' ', ' ', ' ', '*', ' ', ' ', '*', ' ', '*'},
  28. {'*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', ' ', '*'},
  29. {'*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '*'},
  30. {'*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*'}
  31. };
  32. char bludiskoMax[8][13];
  33. int dlzkamax = 0;
  34.  
  35.  
  36. // Predlzi cestu o volne policko so suradnicami (x, y) a rekurzivne bude hladat dalsie predlzenie.
  37. // Ak nie je predlzenie mozne - overi, ci nie je cesta doteraz najdlhsia.
  38. void predlzCestu(int x, int y, int dlzkaCesty)
  39. {
  40. bludisko[x][y] = '.';
  41. if (bludisko[x][y - 1] == ' ' || bludisko[x][y + 1] == ' ' || bludisko[x - 1][y] == ' ' || bludisko[x + 1][y] == ' ')
  42. {
  43. //cestu mozno predlzit
  44. if (bludisko[x][y - 1] == ' ') {
  45. predlzCestu(x, y - 1, dlzkaCesty+1);
  46. }
  47. if (bludisko[x][y + 1] == ' ') {
  48. predlzCestu(x, y + 1, dlzkaCesty+1);
  49. }
  50. if (bludisko[x - 1][y] == ' ') {
  51. predlzCestu(x - 1, y, dlzkaCesty+1);
  52. }
  53. if (bludisko[x + 1][y] == ' ') {
  54. predlzCestu(x + 1, y, dlzkaCesty+1);
  55. }
  56. }
  57. else
  58. {
  59. //cestu nemozno predlzit
  60. if (dlzkaCesty > dlzkamax)
  61. {
  62. dlzkamax = dlzkaCesty;
  63. for (int i = 0; i < m; i++) {
  64. for (int j = 0; j < n; j++)
  65. {
  66. bludiskoMax[i][j] = bludisko[i][j];
  67. }
  68.  
  69. }
  70. }
  71. }
  72. //navrat spat
  73. bludisko[x][y] = ' ';
  74. }
  75.  
  76.  
  77. int main()
  78. {
  79. int i, j;
  80. // Vypis bludiska
  81. for (i = 0; i < m; i++) {
  82. for (j = 0; j < n; j++)
  83. cout << bludisko[i][j];
  84. cout << endl;
  85. }
  86. int x, y;
  87. for (i = 0; i < m; i++) {
  88. for (j = 0; j < n; j++)
  89. {
  90. if (bludisko[i][j] == '+')
  91. {
  92. x = i;
  93. y = j;
  94. }
  95. }
  96. }
  97. if (bludisko[x][y - 1] == ' ') {
  98. predlzCestu(x, y - 1, 1);
  99. }
  100. if (bludisko[x][y + 1] == ' ') {
  101. predlzCestu(x, y + 1, 1);
  102. }
  103. if (bludisko[x-1][y] == ' ') {
  104. predlzCestu(x - 1, y, 1);
  105. }
  106. if (bludisko[x+1][y] == ' ') {
  107. predlzCestu(x + 1, y, 1);
  108. }
  109. cout << dlzkamax << endl;
  110. for (i = 0; i < m; i++) {
  111. for (j = 0; j < n; j++)
  112. cout << bludiskoMax[i][j];
  113. cout << endl;
  114. }
  115. return 0;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement