Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // bludisko.cpp : This file contains the 'main' function. Program execution begins and ends there.
- //
- /*
- Mate k dispozicii bludisko definovane v stvorcekovej sieti takto:
- -steny labyrintu su zapisane znakom *;
- -medzery vyjadruju policka, cez ktore sa da prechadzat;
- -znak + oznacuje startovaciu poziciu hraca.
- Napiste program, ktory pomocou backtrackingu najde v tomto labyrinte najdlhsiu cestu.
- Hrac zacina v startovacom policku a na ziadne policko nevstupi viackrat.
- Skoncit s cestou moze na hociktorom policku.
- Program vypise riesenie do textovej plochy, pricom policka, cez ktore prejde, vypise ako znak '.'
- */
- #include "pch.h"
- #include <iostream>
- using namespace std;
- int m = 8, n = 13; // rozmery bludiska
- // bludisko
- char bludisko[8][13] = {
- {'*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*'},
- {'*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '*'},
- {'*', ' ', '*', '*', '*', '*', ' ', '*', '*', '*', '*', ' ', '*'},
- {'*', ' ', '*', ' ', ' ', '*', ' ', ' ', ' ', ' ', '*', ' ', '*'},
- {'*', ' ', ' ', '+', ' ', ' ', ' ', '*', ' ', ' ', '*', ' ', '*'},
- {'*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', ' ', '*'},
- {'*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '*'},
- {'*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*'}
- };
- char bludiskoMax[8][13];
- int dlzkamax = 0;
- // Predlzi cestu o volne policko so suradnicami (x, y) a rekurzivne bude hladat dalsie predlzenie.
- // Ak nie je predlzenie mozne - overi, ci nie je cesta doteraz najdlhsia.
- void predlzCestu(int x, int y, int dlzkaCesty)
- {
- bludisko[x][y] = '.';
- if (bludisko[x][y - 1] == ' ' || bludisko[x][y + 1] == ' ' || bludisko[x - 1][y] == ' ' || bludisko[x + 1][y] == ' ')
- {
- //cestu mozno predlzit
- if (bludisko[x][y - 1] == ' ') {
- predlzCestu(x, y - 1, dlzkaCesty+1);
- }
- if (bludisko[x][y + 1] == ' ') {
- predlzCestu(x, y + 1, dlzkaCesty+1);
- }
- if (bludisko[x - 1][y] == ' ') {
- predlzCestu(x - 1, y, dlzkaCesty+1);
- }
- if (bludisko[x + 1][y] == ' ') {
- predlzCestu(x + 1, y, dlzkaCesty+1);
- }
- }
- else
- {
- //cestu nemozno predlzit
- if (dlzkaCesty > dlzkamax)
- {
- dlzkamax = dlzkaCesty;
- for (int i = 0; i < m; i++) {
- for (int j = 0; j < n; j++)
- {
- bludiskoMax[i][j] = bludisko[i][j];
- }
- }
- }
- }
- //navrat spat
- bludisko[x][y] = ' ';
- }
- int main()
- {
- int i, j;
- // Vypis bludiska
- for (i = 0; i < m; i++) {
- for (j = 0; j < n; j++)
- cout << bludisko[i][j];
- cout << endl;
- }
- int x, y;
- for (i = 0; i < m; i++) {
- for (j = 0; j < n; j++)
- {
- if (bludisko[i][j] == '+')
- {
- x = i;
- y = j;
- }
- }
- }
- if (bludisko[x][y - 1] == ' ') {
- predlzCestu(x, y - 1, 1);
- }
- if (bludisko[x][y + 1] == ' ') {
- predlzCestu(x, y + 1, 1);
- }
- if (bludisko[x-1][y] == ' ') {
- predlzCestu(x - 1, y, 1);
- }
- if (bludisko[x+1][y] == ' ') {
- predlzCestu(x + 1, y, 1);
- }
- cout << dlzkamax << endl;
- for (i = 0; i < m; i++) {
- for (j = 0; j < n; j++)
- cout << bludiskoMax[i][j];
- cout << endl;
- }
- return 0;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement