SHARE
TWEET

Untitled

a guest Apr 24th, 2019 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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;
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
 
Top