1

Тема: Знаходження найкоротшого виходу з лабіринту, за допомогою рекурсії

Задано лабіринт квадратної форми розміром 6 на 6. Задано точку своїми
координатами – початкове місцезнаходження людини. На карті
лабіринту одиницею визначена стіна лабіринту, нулем – прохід,
цифрою 9 – вихід. Рухатись можна вперед, назад, вправо та вліво. За
скільки кроків людина вийде з лабіринту, якщо вихід один?

Карту (структуру) лабіринту завантажувати з файлу map.txt. У структурі
лабіринту передбачити наявність зовнішніх стін, які відображаються у
файлі. Обробку масиву-карти НЕ реалізовувати глобальним масивом, а
передачею посилання. Початкові координати людини отримувати з
клавіатури. Передбачити можливість повідомлення користувача, про
уведені ним некоректні початкові координати. Задачу розв’язати за
допомогою рекурсивних функцій.

map.txt :
1 1 1 1 1 1 1 1
1 0 0 1 0 1 0 1
1 1 0 0 0 1 0 1
1 0 0 1 0 0 0 1
1 0 1 0 0 1 1 1
1 1 1 1 0 0 0 1
1 9 0 0 0 1 1 1
1 1 1 1 1 1 1 1

2

Re: Знаходження найкоротшого виходу з лабіринту, за допомогою рекурсії

Усе погано

3

Re: Знаходження найкоротшого виходу з лабіринту, за допомогою рекурсії

На якій мові має бути реалізована програма? С або С++? Немає в завданні.
Де буде початок, координата [0,0]? Немає в завданні.
В завданні розмір лабіринту 6х6, а файл 8х8
У якому вигляді буде зберігатись лабіринт? Є в завданні.

Відкриваємо Visual Studio.
Створюємо новий консольний проект, маємо...

#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

Далі розбиваємо задачу на меньші задачі:

Прочитати дані з текстового файлу.
Створити лабіринт.
Отримати координати від користувача.
Перевірити правильність вводу.
Знайти вихід з лабіринту.

Оголошуємо необхідні функці:

#include <iostream>

//прочитати дані про лабіринт з текстового файлу
template <typename table>
bool ReadMaze(const std::string& fullPath, table& maze);
//отримати координати від користувача
template <typename table>
bool GetXY(unsigned int& x, unsigned int& y, const table& maze);
//Знайти вихід з лабіринту
template <typename table>
bool MazeWayOut(table& maze, unsigned int point_r, unsigned int point_c);
//Вивести лабіринт із знайденим шляхом
template <typename table>
void PrintMazeWayOut(table& maze);

int main()
{
    const int rows = 8; //довжина лабіринту
    const int cols = 8; //ширина лабіринту
    unsigned int point_r = 0;
    unsigned int point_c = 0;
    int maze[rows][cols] = { 0 }; //лабіринт
    if (ReadMaze("d:\\map.txt", maze))
    {
        if (GetXY(point_r, point_c, maze))
        {
            if(MazeWayOut(maze, point_r, point_c))
                PrintMazeWayOut(maze);
        }
    }
    return 0;
}

Потім користуючись пошуком знаходимо:
Алгоритм розв'язування лабіринтів
https://uk.wikipedia.org/wiki/%D0%90%D0 … 1%96%D0%B2

В цій реалізації використовується два додаткових масиви для відвіданих точок і знайденого шляху
Я вирішив їх не використовувати і модифікувати значення в заданому лабіринті

Так само знаходимо, як отримати число з клавіатури?
Як прочитати текстовий файл?

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

//прочитати дані про лабіринт з текстового файлу
template <typename table>
bool ReadMaze(const std::string& fullPath, table& maze);
//отримати координати від користувача
template <typename table>
bool GetXY(unsigned int& x, unsigned int& y, const table& maze);
//Знайти вихід з лабіринту
template <typename table>
bool MazeWayOut(table& maze, unsigned int point_r, unsigned int point_c);
//Вивести лабіринт із знайденим шляхом
template <typename table>
void PrintMazeWayOut(table& maze);

int main()
{
    const int rows = 8; //довжина лабіринту, в завданні 6
    const int cols = 8; //ширина лабіринту, в завданні 6
    unsigned int point_r = 0;
    unsigned int point_c = 0;
    int maze[rows][cols] = { 0 }; //лабіринт
    if (ReadMaze("d:\\map.txt", maze))
    {
        if (GetXY(point_r, point_c, maze))
        {
            if(MazeWayOut(maze, point_r, point_c))
                PrintMazeWayOut(maze);
        }
    }
    return 0;
}

template <typename table>
bool ReadMaze(const std::string& fullPath, table& maze)
{
    bool result = true;
    const int rows = sizeof(maze) / sizeof(maze[0]);
    const int cols = sizeof(maze[0]) / sizeof(maze[0][0]);

    unsigned int x = 0;
    unsigned int y = 0;

    std::string line;
    ifstream mazeFile(fullPath);
    if (mazeFile.is_open())
    {
        while (getline(mazeFile, line))
        {
            std::cout << line << std::endl;
            x = 0;
            for (size_t i = 0; i < line.length(); i++)
            {
                if (line[i] == '0')
                {
                    maze[y][x] = 0;
                    x++;
                }
                else if (line[i] == '1')
                {
                    maze[y][x] = 1;
                    x++;
                }
                else if (line[i] == '9')
                {
                    maze[y][x] = 9;
                    x++;
                }
                if (x >= cols)
                    break;
            }
            y++;
            if (y >= rows)
                break;
        }
        std::cout << std::endl;
        mazeFile.close();
    }
    else
    {
        std::cout << "Unable to open file" << std::endl;
        result = false;
    }

    return result;
}

template <typename table>
bool GetXY(unsigned int& x, unsigned int& y, const table& maze)
{
    bool result = false;
    const int rows = sizeof(maze) / sizeof(maze[0]);
    const int cols = sizeof(maze[0]) / sizeof(maze[0][0]);
    //тут має бути введення з клавіатури
    x = 1;
    y = 1;
    //перевірка вводу
    if (x < rows && y < cols && maze[y][x] != 1) //1 - стіна
    {
        result = true;
        std::cout << "Start point x = " << x << ", y = " << y << std::endl;
        std::cout << std::endl;
    }
    else
    {
        std::cout << "Wrong point" << std::endl;
    }
    return result;
}

//2 - відвідана точка
//3 - знайдений шлях
template <typename table>
bool MazeWayOut(table& maze, unsigned int point_r, unsigned int point_c)
{
    const int rows = sizeof(maze) / sizeof(maze[0]);
    const int cols = sizeof(maze[0]) / sizeof(maze[0][0]);
    if (maze[point_c][point_r] == 9)
    {
        maze[point_c][point_r] = 3;
        return true;
    }
    if (maze[point_c][point_r] == 1 || maze[point_c][point_r] >= 2)
        return false;
    if(!maze[point_c][point_r])
        maze[point_c][point_r] = 2;
    if(point_r != 0)
    {
        if (MazeWayOut(maze, point_r - 1, point_c)) {
            maze[point_c][point_r] = 3;
            return true;
        }
    }
    if (point_r < (rows - 1))
    {
        if (MazeWayOut(maze, point_r + 1, point_c)) {
            maze[point_c][point_r] = 3;
            return true;
        }
    }
    if (point_c != 0)
    {
        if (MazeWayOut(maze, point_r, point_c - 1)) {
            maze[point_c][point_r] = 3;
            return true;
        }
    }
    if (point_c < (cols - 1))
    {
        if (MazeWayOut(maze, point_r, point_c + 1)) {
            maze[point_c][point_r] = 3;
            return true;
        }
    }
    return false;
}

template <typename table>
void PrintMazeWayOut(table& maze)
{
    const int rows = sizeof(maze) / sizeof(maze[0]);
    const int cols = sizeof(maze[0]) / sizeof(maze[0][0]);
    for (int y = 0; y < cols; y++)
    {
        for (int x = 0; x < rows; x++)
        {
            if (maze[y][x] == 2)//просто відвідані точки
                maze[y][x] = 0;
            std::cout << maze[y][x] << " ";
        }
        std::cout << endl;
    }
}

Для лабіринту
1 1 1 1 1 1 1 1
1 0 0 1 0 1 0 1
1 1 0 0 0 1 0 1
1 0 0 1 0 0 0 1
1 0 1 0 0 1 1 1
1 1 1 1 0 0 0 1
1 9 0 0 0 1 1 1
1 1 1 1 1 1 1 1

і точки (1,1)

знайдено шлях

1 1 1 1 1 1 1 1
1 3 3 1 0 1 0 1
1 1 3 3 3 1 0 1
1 0 0 1 3 0 0 1
1 0 1 0 3 1 1 1
1 1 1 1 3 0 0 1
1 9 3 3 3 1 1 1
1 1 1 1 1 1 1 1

Подякували: Betterthanyou, leofun01, Bobby3

4

Re: Знаходження найкоротшого виходу з лабіринту, за допомогою рекурсії

Можете, будь ласка, пояснити для чого Ви використали template?

5

Re: Знаходження найкоротшого виходу з лабіринту, за допомогою рекурсії

Bobby написав:

Можете, будь ласка, пояснити для чого Ви використали template?

Щоб показати який він крутий і які складні концепції знає.

6

Re: Знаходження найкоротшого виходу з лабіринту, за допомогою рекурсії

koala написав:
Bobby написав:

Можете, будь ласка, пояснити для чого Ви використали template?

Щоб показати який він крутий і які складні концепції знає.

А може ви можете пояснити, будь ласка, що воно означає? І чи можна якось замінити?

7

Re: Знаходження найкоротшого виходу з лабіринту, за допомогою рекурсії

Bobby написав:

А може ви можете пояснити, будь ласка, що воно означає? І чи можна якось замінити?

Вам поставили купу питань - причому для того, щоб вам допомогти. Ви їх ігноруєте. Чому ви вирішили, що до ваших питань ставитимуться краще? Тим більше, що ваші питання не мають на меті комусь допомогти.

8

Re: Знаходження найкоротшого виходу з лабіринту, за допомогою рекурсії

koala написав:
Bobby написав:

А може ви можете пояснити, будь ласка, що воно означає? І чи можна якось замінити?

Вам поставили купу питань - причому для того, щоб вам допомогти. Ви їх ігноруєте. Чому ви вирішили, що до ваших питань ставитимуться краще? Тим більше, що ваші питання не мають на меті комусь допомогти.

Вибачте, я не відповів, бо те, що питав rb.fedor, він зробив саме так, як і треба було, я просто хотів дізнатися, для чого template, і чи можна його якось замінити

9

Re: Знаходження найкоротшого виходу з лабіринту, за допомогою рекурсії

rb.fedor, ви відповідаєте за тих, кого приручили.