Тема: Графи

Маю завдання, але не розумію як до нього підійти, з чого почати... Як це реалізувати, в інтернеті практично не має інформації.  Дерево, стек, список, принципі на логіку робилось а тут...Підкажіть будь ласка з чого хоча б почати.


У замку Stonehandge юний принц не поладив зі своєю гувернанткою в кімнаті, де вони снідали. Для запобігання покарання принц вирішив сховатися в одній з кімнат замку. Рухаючись з кімнати в кімнату, принц обов'язково закривав на ключ двері, через які він пройшов, після чого ні він, ні гувернантка не могли скористатися цими дверима. Через будь-яку кімнату (у тому числі і через ту, у якій знаходиться гувернантка) принц може проходити кілька разів, якщо це дозволяють ще не замкнені їм двері. Споконвічно всі двері в замку не замкнені. Між двома кімнатами замку не більше однієї двері. Загальна кількість дверей не перевершує 5000.  Гувернантка починає шукати принца тільки після того, як він сховався. Уникнути покарання принц може тільки в тому випадку, якщо гувернантка, проходячи через незамкнені двері, що залишилися, не зуміє потрапити в кімнату, де він сховався.  Написати програму, що визначає, чи зможе принц сховатись від гувернантки, і якщо це вдасться, то запропонуйте йому кожний з можливих шляхів порятунку.

2

Re: Графи

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

3

Re: Графи

"Споконвічно" - це, я так розумію, "изначально" було? Дещо перебрали з драматичністю.
Взагалі на 5000 дверей кожен з можливих шляхів, я так розумію, це трохи забагато.
Гадаю, вам треба трохи помікувати над ейлеровими ланцюгами. Детальніше отут, наприклад.

4 Востаннє редагувалося tchort (07.11.2020 20:10:51)

Re: Графи

Класика. Пошукайте "maze solving C++" або "solving maze problem C++".
Чи призводять зміни стану "лабіринт кімнат" об'єктом А до такого сану "лабіринт кімнат" де об'єкт Б не може отримати вирішення. (вирішення=вихід=координати об'єкта А).
https://rosettacode.org/wiki/Maze_solving#C.2B.2B
https://www.cs.bu.edu/teaching/alg/maze/
http://www.cplusplus.com/forum/beginner/218539/
https://stackoverflow.com/questions/919 … -c#9192067

Re: Графи

tchort написав:

Класика. Пошукайте "maze solving C++" або "solving maze problem C++".
Чи призводять зміни стану "лабіринт кімнат" об'єктом А до такого сану "лабіринт кімнат" де об'єкт Б не може отримати вирішення. (вирішення=вихід=координати об'єкта А).
https://rosettacode.org/wiki/Maze_solving#C.2B.2B
https://www.cs.bu.edu/teaching/alg/maze/
http://www.cplusplus.com/forum/beginner/218539/
https://stackoverflow.com/questions/919 … -c#9192067

Дякую. Попробую

6

Re: Графи

Нащо проходження лабіринту, якщо для гувернантки це банальна задача на зв'язність? Нам не треба будувати шлях гувернантки, нам треба лише сказати "зможе" чи "не зможе".
А от для принца... Спробуємо побудувати "замок" з абсурдною відповіддю. Отже, замок складається з двох повних графів по 63 кімнати (з кожної кімнати повного графа до кожної іншої ведуть одні двері), які пов'язані лише 3 дверима - між кімнатами A-A`,B-B`, C-C`. Кількість дверей дорівнює 63*62/2 * 2 + 3 = 3909<5000. Принц і гувернантка снідають у тій частині замку, де знаходяться ці 3 кімнати, і не в одній з них. Розглянемо такий шлях принца: він пробігає 10 різних кімнат навмання, крім A,B і C (це можна зробити 59*58*..51*50 способами) і переходить до кімнати A, звідти до A`. Далі знову пробігає 10 кімнат навмання 60*59*...*51 способами, переходить до B` і до B. Відвідує 10 ще невідвіданих кімнат 49*48*...*40 способами, переходить до C і до C` - і знову 10 невідвіданих кімнат 50*49*48*...*41 способами. В результаті гувернантка його не спіймає: їй треба пройти одну з дверей A-A`, B-B` чи C-C`, щоб потрапити до другої половини замку, але ці двері замкнені. Разом у принца вийшло 68-значне число можливих шляхів, і очевидно, що це лише маленька дещиця усіх можливих шляхів до порятунку; але якщо програму запустити на комп'ютері, що витрачає 1пс на один варіант, то за час існування Всесвіту він зміг би запропонувати лише 29-значне число варіантів.
Спробуйте не заганяти умову в автоперекладач, а розібрати її - може, тоді щось і зрозумієте, як робити. Бо зараз умова абсурдна.

Подякували: tchort1

Re: Графи

koala написав:

Нащо проходження лабіринту, якщо для гувернантки це банальна задача на зв'язність? Нам не треба будувати шлях гувернантки, нам треба лише сказати "зможе" чи "не зможе".
А от для принца... Спробуємо побудувати "замок" з абсурдною відповіддю. Отже, замок складається з двох повних графів по 63 кімнати (з кожної кімнати повного графа до кожної іншої ведуть одні двері), які пов'язані лише 3 дверима - між кімнатами A-A`,B-B`, C-C`. Кількість дверей дорівнює 63*62/2 * 2 + 3 = 3909<5000. Принц і гувернантка снідають у тій частині замку, де знаходяться ці 3 кімнати, і не в одній з них. Розглянемо такий шлях принца: він пробігає 10 різних кімнат навмання, крім A,B і C (це можна зробити 59*58*..51*50 способами) і переходить до кімнати A, звідти до A`. Далі знову пробігає 10 кімнат навмання 60*59*...*51 способами, переходить до B` і до B. Відвідує 10 ще невідвіданих кімнат 49*48*...*40 способами, переходить до C і до C` - і знову 10 невідвіданих кімнат 50*49*48*...*41 способами. В результаті гувернантка його не спіймає: їй треба пройти одну з дверей A-A`, B-B` чи C-C`, щоб потрапити до другої половини замку, але ці двері замкнені. Разом у принца вийшло 68-значне число можливих шляхів, і очевидно, що це лише маленька дещиця усіх можливих шляхів до порятунку; але якщо програму запустити на комп'ютері, що витрачає 1пс на один варіант, то за час існування Всесвіту він зміг би запропонувати лише 29-значне число варіантів.
Спробуйте не заганяти умову в автоперекладач, а розібрати її - може, тоді щось і зрозумієте, як робити. Бо зараз умова абсурдна.

Так це метода львівської політехніки (мені здається вона вкрадена з якогось російського сайту або джерела). Який перекладач... Хочете можу Вам файлом скинути. Те що Ви озвучили дуже складно (особисто для мене) а от лабіринтиком це і зрозуміло і реалізувати можливо. Такі справи.

8

Re: Графи

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

9

Re: Графи

Нехай кімнати це вузли графа, а двері між ними це ребра графа. Граф неорієнтовний.
Незрозуміло з якої кімнати починає пошук гувернантка.

Якщо гувернантка спауниться в будь-якій кімнаті то
Принцу треба тікати в "листовий" вузол - кімната з одними дверима.

Якщо гувернантка починає з тієї ж кімнати що і принц то
Гувернантка може зайти в кімнату де принц через інші двері, іншим шляхом тільки тоді коли граф має цикли. Тобто принцу достатньо заховатись в кімнаті, вузлі графа, який не належить циклу. Якщо граф дуже насичений і має цикли то принц повинен проходити такими шляхами щоб розривати цикли, закриваючи двері, тобто видаляючи ребра графа

Це все можливо умови обізнаності, тобто принц знає весь граф.

Подякували: Chemist-i, leofun012

10 Востаннє редагувалося tchort (07.11.2020 22:32:30)

Re: Графи

Здається я неправильно інтерпретував задачу в такому разі, зробивши деяких припущень. Мутно і неоднозначно описано. Коли все це буквально передруковано з підручника - мої вам співчуття.

11 Востаннє редагувалося koala (07.11.2020 23:58:25)

Re: Графи

Обдумав задачу. Якщо там усе ж таки "будь-який", а не "кожний", то порада пана tchort вам згодиться.

Отже, алгоритм буде такий (псевдокод):

якщо немає кімнат із непарною кількістю дверей:
    вивести "Не зможе" #цикл Ейлера
інакше:
    сховок = кімната з найменшою непарною кількістю дверей, до якої може дістатися принц, крім їдальні
    пройти з їдальні у сховок #у сховку тепер парна кількість відчинених дверей
    поки існує шлях з їдальні у сховок:
        якщо існує шлях зі сховку у сховок:
            пройти зі сховку у сховок #знову парна кількість дверей
        інакше: 
            перевірити, за якою з дверей немає шляху до їдальні #якщо є шлях з двох дверей - є шлях зі сховку до сховку
            пройти за ці двері
            вийти з циклу
    вивести шлях
Подякували: Arete1

12 Востаннє редагувалося Львовский сырник в мульти (11.11.2020 20:22:20)

Re: Графи

Як тепер реалізувати всі можливі варіанти для схованки принца? Ніби додати або відняти на 1 його положення в матриці? І так до кінця масиву? Підкажіть будь ласка. Алгоритм для сховку принципі намалював і реалізував, але як тепер всі варіанти знайти не знаю...

#include <iostream>
#include <conio.h>
using namespace std;
void algorithm(char***matrix,int M,int N) {
    char** run = *matrix;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (run[i][j] == '^') {
                if (!(run[i][j + 2] && run[i][j] != '#')) {
                    run[i][j] = run[i][j];
                }
                else {
                    run[i][j + 1] = '#';
                    run[i][j] = '*';
                    run[i][j + 2] = '^';
                } if (!(run[i - 2][j + 2] && run[i - 2][j + 2] != '#')) {
                    run[i][j] = run[i][j];
                }
                else {
                    run[i - 1][j + 2] = '#';
                    run[i][j + 2] = '*';
                    run[i - 2][j + 2] = '^';
                }
                if (!(run[i - 2][j] && run[i - 2][j] != '#')) {
                    run[i][j] = run[i][j];
                }
                else {
                    run[i - 2][j + 1] = '#';
                    run[i - 2][j + 2] = '*';
                    run[i - 2][j] = '^';
                }
                if (!(run[i][j] && run[i][j] != '#')) {
                    run[i][j] = run[i][j];
                }
                else {
                    run[i - 1][j] = '#';
                    run[i][j] = '^';
                    run[i - 2][j] = '*';
                }
                if (!(run[i + 2][j] && run[i + 2][j] != '#')) {
                    run[i][j] = run[i][j];
                }
                else {
                    run[i + 1][j] = '#';
                    run[i + 2][j] = '^';
                    run[i][j] = '*';
                }
                if (!(run[i + 2][j - 2] && run[i + 2][j - 2] != '#')) {
                    run[i][j] = run[i][j];
                }
                else {
                    run[i + 2][j - 1] = '#';
                    run[i + 2][j - 2] = '^';
                    run[i + 2][j] = '*';
                }
                if (!(run[i][j - 2] && run[i + 2][j - 2] != '#')) {
                    run[i][j] = run[i][j];
                }
                else {
                    run[i + 1][j - 2] = '#';
                    run[i][j - 2] = '^';
                    run[i][j - 2] = '*';
                }
                if (!(run[i][j] && run[i][j] != '#')) {
                    run[i][j] = run[i][j];
                }
                else {
                    run[i][j - 1] = '#';
                    run[i][j] = '^';
                    run[i][j - 1] = '*';
                }
            }
            
        }
    }
}


void prince(char*** matrix,int M, int N) {
    char** prince = *matrix;
    cout << "Введіть номер кімнати: ";
    int num;
    cin >> num;
    if (num <= N ) {
        num = num + N;
    }
    else {
        if (num >= ((N * M )- N)) {
            num = num - N-3;
            if (num % 2 == 0) {
                num = num + 1; // Щоб не розмістити принца в стіні.
            }
        }
        else {
            if (num % 2 == 0) {
                num = num + 1; // Щоб не розмістити принца в стіні.
            }
        }
        
    }

    int find = 0;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (find == num) {
                prince[i][j] = '^';
                
            }
            find = find + 1;
        }
    }
    
}
int main(void) {
    setlocale(LC_ALL, "Ukr");
    int M;
    int N;
    int i, j;
    char** matrix = nullptr;
    char** governess = nullptr;
    cout << "Введіть довжину та ширину (1 до 1) замку: ";
    cin >> M;
    cin >> N;

    matrix = new char* [M];
    for (i = 0; i < M; i++) {
        matrix[i] = new char[N];

    }
    for (i = 0; i < M; i++) {
        for (j = 0; j < N; j++) {


            if (i == 0 || i == M-1) {
                matrix[i][j] = '#';
            }
            else {
                if (j == 0 || j == N-1) {
                    matrix[i][j] = '#';
                }
                else {
                    if (i % 2 == 0 && j % 2 == 0) {
                        matrix[i][j] = '#';
                    }
                    else {
                        if (i % 2 != 0) {
                            matrix[i][j] = '*';
                        }
                        else {
                            if (i != 0 && i != N-1 && i % 2 == 0 && j % 2 == 0) {
                                matrix[i][j] = '#';
                            }
                            else {
                                if (i != 0 && i != N-1 && i % 2 == 0 && j % 2 != 0) {
                                    matrix[i][j] = '*';
                                }
                            }
                        }
                    }



                }
            }
        }
    }
    prince(&matrix, M, N);
    for (i = 0; i < M; i++) {
        for (j = 0; j < N; j++) {

            cout << matrix[i][j];
        }
        cout << endl;
    }
    cout << endl;
    algorithm(&matrix, M, N);
    
    
    for (i = 0; i < M; i++){
        for (j = 0; j < N; j++){
        
            cout << matrix[i][j];
        }
    cout << endl;
    }

    

    _getch();
    return 0;
}

13

Re: Графи

Будь ласка, не плодіть теми. Одна задача - одна тема, п. 3.6 Правил.

Гадаю, ви обрали недоречну структуру даних для цієї задачі. Я правильно зрозумів, що ви маєте на увазі намалювати план замку на площині символами? В умові ані слова про планарність немає, а значками ви лише планарний граф намалюєте. Припустимо, у замку 5 кімнат, і з кожної в кожну ведуть двері - просто деякі з кімнат двоповерхові, зі сходами. Як ви такий замок зробите? З іншого боку, у вас поняття "кімната" перетворюється на щось дуже складне. Принц зайшов до кімнати - як йому шукати, чи є ще в ній незачинені двері? Якимось складним алгоритмом?
Як на мене, найзручніше представити замок матрицею суміжності. Принц пройшов двері - ставимо 0 у відповідні комірки.

14

Re: Графи

Ось частина умови оригінальної задачі(?), яку вам чомусь не дали:

Google translate написав:

Вхідні дані
У вхідному файлі castle.in міститься план замку.
У першому рядку вхідного файлу знаходиться натуральне число N (1 <N <1 000) - кількість кімнат.
У другому рядку вхідного файлу міститься нат. число K (1 <= K <= N) - номер кімнати, в якій принц і гувернантка снідали.
У наступних N рядках містяться списки суміжних кімнат: в i-ому рядку перераховані через пробіл номери кімнат, суміжних з i-ою кімнатою. Кожен такий рядок закінчується нулем.

Вихідні дані
Вихідний файл з ім'ям castle.out повинен містити наступну інформацію. Якщо принц не зможе уникнути покарання, в єдиному рядку файлу виводиться повідомлення No. В протилежному випадку, в першому рядку файлу виводиться повідомлення Yes, у другому рядку - кількість дверей, закритих принцом, а в третьому рядку - послідовність номерів кімнат, розділених пробілами, в яких побував принц.

Приклад вхідного файлу
4
1
2 4 0
4 1 3 0
2 4 0
1 2 3 0

Приклад вихідного файлу для наведеного прикладу вхідного файлу
Yes
3
1 4 2 3

Re: Графи

koala написав:

Ось частина умови оригінальної задачі(?), яку вам чомусь не дали:

Google translate написав:

Вхідні дані
У вхідному файлі castle.in міститься план замку.
У першому рядку вхідного файлу знаходиться натуральне число N (1 <N <1 000) - кількість кімнат.
У другому рядку вхідного файлу міститься нат. число K (1 <= K <= N) - номер кімнати, в якій принц і гувернантка снідали.
У наступних N рядках містяться списки суміжних кімнат: в i-ому рядку перераховані через пробіл номери кімнат, суміжних з i-ою кімнатою. Кожен такий рядок закінчується нулем.

Вихідні дані
Вихідний файл з ім'ям castle.out повинен містити наступну інформацію. Якщо принц не зможе уникнути покарання, в єдиному рядку файлу виводиться повідомлення No. В протилежному випадку, в першому рядку файлу виводиться повідомлення Yes, у другому рядку - кількість дверей, закритих принцом, а в третьому рядку - послідовність номерів кімнат, розділених пробілами, в яких побував принц.

Приклад вхідного файлу
4
1
2 4 0
4 1 3 0
2 4 0
1 2 3 0

Приклад вихідного файлу для наведеного прикладу вхідного файлу
Yes
3
1 4 2 3

Але ж мені потрібно його якось загнати в тупік... І порахувати можливі варіанти. Якщо по матриці суміжності рухатись, то получится, напевно, хаотичний рух, який ні до чого не приведе. Чи я помиляюсь... Бо думав як це реалізувати, і прийшов до висновку що потрібно рухатись "вісімкою під кутом 45°". Якщо хоча б одна із дверей зачинена, то принц не зможе фактично себе зачинити.

Re: Графи

І якщо Вам не складно, підкажіть де можна почитати про проходження графу. Бо я не можу знайти як це робити.

17 Востаннє редагувалося koala (11.11.2020 21:50:33)

Re: Графи

А ваша матриця від графу відрізняється лише тим, що в її елементів максимум 4 сусіди - зверху, знизу, ліворуч, праворуч. І клітина відповідає кімнаті. А так усе лишається так само. Малювати менше, загальність вища. Ви (боюся, за порадою пана tchort) надто зациклилися на конкретному представленні. Як проходити - що матрицю, що масив? Наприклад, хвильовим алгоритмом: позначаєте (в допоміжному масиві) всі суміжні з поточною кімнати одиничками, всі непозначені, сусідні з одиницями - двійками і т.д., доки не дійдете до потрібної кімнати. А тоді відновлюєте шлях, переходячи по кроку назад. І зачиняєте на цьому шляху двері.

18 Востаннє редагувалося Львовский сырник в мульти (03.12.2020 21:03:46)

Re: Графи

Переробив я повністю код за Вашою порадою. Але як найти всі можливі варіанти ходів? І функція minway працює якось криво...Не розумію в чому її проблема.

#include <conio.h>
#include <iostream>
using namespace std;


void printcastle(char** first, int num) {
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
            cout << first[i][j];
            cout << " ";
        }
        cout << endl;
    }
}
int minway(int j,char*** cast, int num) {
    int* mas = new int[num];
    int min = 10;
    int index = 1;
    char** cas = *cast;
    for (int i = 0; i < num; i++) {
        mas[i] = 1;
    }
    for (int i = 0; i < num; i++) {
        if (cas[j][i] == '1') {
            mas[i] = 1;
        }
        else {
            if (cas[j][i] == '2') {
                mas[i] = 2;
            }
            else {
                if (cas[j][i] == '3') {
                    mas[i] = 3;
                }
                else {
                    if (cas[j][i] == '4') {
                        mas[i] = 4;
                    }
                    else {
                        if (cas[j][i] == '5') {
                            mas[i] = 5;
                        }
                        else {
                            if (cas[j][i] == '0' || cas[j][i] =='^') {
                                mas[i] = 6;
                            }
                        }
                    }
                }
            }
        }
    }

    for (int i = 0; i < num; i++) {
        if (mas[i] < min) {
            min = mas[i];
            index = i +1;
        }
    }
    
    return index;
}
void run(char*** cast, int num) {
    char** cas = *cast;
    
    
        for (int i = 0; i < num; i++) {
            
            for (int j = 0; j < num; j++) {
                if (cas[i][j] == '^') {
                    
                    
                    for (int n =0; n < 10; n++) {
                        if (cas[i][n] == '1') {
                            cas[i][j] = '0';
                            cas[n][n] = '^';
                            cas[i][n] = '0';
                            cas[n][i] = '0';
                            printcastle(*cast, num);
                            cout << endl;

                            return;

                        }
                        else {
                            if (cas[i][n] == '2') {
                                cas[i][j] = '0';
                                cas[n][n] = '^';
                                cas[i][n] = '0';
                                cas[n][i] = '0';
                                printcastle(*cast, num);
                                cout << endl;
                                return;

                            }
                            else {
                                if (cas[i][n] == '3') {
                                    cas[i][j] = '0';
                                    cas[n][n] = '^';
                                    cas[i][n] = '0';
                                    cas[n][i] = '0';
                                    printcastle(*cast, num);
                                    cout << endl;
                                    return;

                                }
                                else {
                                    if (cas[i][n] == '4') {
                                        cas[n][n] = '^';
                                        cas[i][n] = '0';
                                        cas[i][j] = '0';
                                        cas[n][i] = '0';
                                        printcastle(*cast, num);
                                        cout << endl;
                                        return;
                                    }
                                    else {
                                        if (cas[i][n] == '5') {
                                            cas[n][n] = '^';
                                            cas[i][n] = '0';
                                            cas[i][j] = '0';
                                            cas[n][i] = '0';
                                            printcastle(*cast, num);
                                            cout << endl;

                                            return;
                                        }
                                        else {
                                            if (cas[i][n] == '0' || cas[i][n] == '^') {
                                                n = n;
                                            }
                                        }


                                    }
                                }
                            }
                        }

                    }
                }
                
            }

        }

}


int main(void){
    setlocale(LC_ALL, "Ukr");
    int num;
    int rum;

    char** cas = nullptr; 
    cout << "Введіть к-сть кімнат у замку: ";
    cin >> num;
    if (cas == nullptr) {
        cas = new char* [num];
        for (int i = 0; i < num; i++) {
            cas[i] = new char[num];
        }
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                    int room;
                    room = rand() % 6;
                    if (room == 0) {
                        cas[i][j] = '0';
                        cas[j][i] = '0';
                    }
                    else {
                        if (room == 1) {
                            cas[i][j] = '1';
                            cas[j][i] = '1';
                        }
                        else {
                            if (room == 2) {
                                cas[i][j] = '2';
                                cas[j][i] = '2';
                            }
                            else {
                                if(room == 3) {
                                    cas[i][j] = '3';
                                    cas[j][i] = '3';
                                }
                                else {
                                    if(room == 4) {
                                        cas[i][j] = '4';
                                        cas[j][i] = '4';
                                    }
                                    else {
                                        if(room == 5) {
                                            cas[i][j] = '5';
                                            cas[j][i] = '5';
                                        }
                                    }
                                }
                            }
                        }
                    }
                
            }
        }
    }


    printcastle(cas, num);
    cout << "Введіть номер кімнати в якій знаходиться принц: ";
    cin >> rum;
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
            if (i == rum - 1 && j == rum - 1) {
                cas[i][j] = '^';

            }
        }
    }
    printcastle(cas, num);
    cout << endl;
    for (int i = 0; i < num * num; i++) {
        run(&cas, num);
    }
    
    
    
    
        

    _getch();
    return 0;
}

Re: Графи

Помилку в фунції поправив. Але так і не придумав алгоритму для пошуку всіх можливих шляхів. Дайте будь ласка підказочку.

20 Востаннє редагувалося Львовский сырник в мульти (04.12.2020 18:53:09)

Re: Графи

І виходить дивна річ... Принц завжди сховається у якійсь кімнаті ... Можливо це така задачка з "підвохом". Не потрібно шукати всі можливі варіанти сховку, якщо гувернантка так чи інакше не знайде принца хыхыхыхыхыхы.

#include <conio.h>
#include <iostream>
using namespace std;
struct way {
    int num; 
    int num2;
    way* next;
};
void queue(way** firstmove,int nu, int nu2) {
    
    if (*firstmove == nullptr) {
        *firstmove = new way;
        (*firstmove)->num = nu;
        (*firstmove)->num2 = nu2;
        (*firstmove)->next = nullptr;
    }
    else {
        way* fm = *firstmove;
        if (fm != nullptr) {
            while (fm->next != nullptr) {
                fm = fm->next;
            }
        }
        fm->next = new way;
        fm = fm->next;
        fm->num = nu;
        fm->num2 = nu2;
        fm->next = nullptr;
    }
    
}
void moway(way** firstmove) {
    int n = 1;
    while ((*firstmove) != nullptr) {
        cout << n << "-ий хід : ";
        cout << " принц перейшов з " << (*firstmove)->num << " кімнати у " << (*firstmove)->num2 << ".";
        cout << endl;
        if ((*firstmove)->next == nullptr) {
            cout << "Принц зачинився у " << (*firstmove)->num2 << "-ій кімнаті. Гувернантка не зможе його знайти." << endl;
        }
        cout << endl;
        (*firstmove) = (*firstmove)->next;
    }    
}
void printcastle(char** first, int num) {
    for (int i = 0; i < num+1; i++) {
        for (int j = 0; j < num+1; j++) {
            if (i == 0 && j == 0) {
                cout << "№";
                cout << " ";
            }
            else {
                if (i == 0 && j < num + 1) {
                    cout << j;
                    cout << " ";
                }
                else {
                    if (j == 0 && i < num + 1) {
                        cout << i;
                        cout << " ";
                    }
                    else {
                        cout << first[i - 1][j - 1];
                        cout << " ";
                    }
                }
            }
        }
        cout << endl;
    }
}
void prince(char*** first, int num,int &rum) {
    char** prince = *first;
    cout << "Введіть номер кімнати в якій знаходиться принц: ";
    cin >> rum;
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
            if (i == rum - 1 && j == rum - 1) {
                prince[i][j] = '^';

            }
        }
    }
}
int minway(int j,char*** cast, int num) {
    int* mas = new int[num];
    int min = 10;
    int index = 1;
    char** cas = *cast;
    for (int i = 0; i < num; i++) {
        if (cas[j][i] == '1') {
            mas[i] = 1;
        }
        else {
            if (cas[j][i] == '2') {
                mas[i] = 2;
            }
            else {
                if (cas[j][i] == '3') {
                    mas[i] = 3;
                }
                else {
                    if (cas[j][i] == '4') {
                        mas[i] = 4;
                    }
                    else {
                        if (cas[j][i] == '5') {
                            mas[i] = 5;
                        }
                        else {
                            if (cas[j][i] == '0' ) {
                                mas[i] = 6;
                            }
                            else {
                                if (cas[j][i] == '^') {
                                    mas[i] = 7;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    for (int i = 0; i < num; i++) {
        if (mas[i] <= min) {
            min = mas[i];
            index = i ;
        }
    }
    
    return index;
}
void run(char*** cast, int num,way **firstmove) {
    
    char** cas = *cast;
        for (int i = 0; i < num; i++) {
            
            for (int j = 0; j < num; j++) {
                if (cas[i][j] == '^') {
                    
                    int n = minway(i, cast, num);
                    

                        if (cas[i][n] == '1') {
                            cas[i][j] = '0';
                            cas[n][n] = '^';
                            cas[i][n] = '0';
                            cas[n][i] = '0';
                            printcastle(*cast, num);
                            cout << endl;
                            cout << i+1 << "->" << n+1 << endl;
                            queue(firstmove, i+1, n+1);
                            return;
                            

                        }
                        else {
                            if (cas[i][n] == '2') {
                                cas[i][j] = '0';
                                cas[n][n] = '^';
                                cas[i][n] = '0';
                                cas[n][i] = '0';
                                printcastle(*cast, num);
                                cout << endl;
                                cout << i + 1 << "->" << n + 1 << endl;
                                queue(firstmove, i + 1, n + 1);
                                return;

                            }
                            else {
                                if (cas[i][n] == '3') {
                                    cas[i][j] = '0';
                                    cas[n][n] = '^';
                                    cas[i][n] = '0';
                                    cas[n][i] = '0';
                                    printcastle(*cast, num);
                                    cout << endl;
                                    cout << i + 1 << "->" << n + 1 << endl;
                                    queue(firstmove, i + 1, n + 1);
                                    return;

                                }
                                else {
                                    if (cas[i][n] == '4') {
                                        cas[n][n] = '^';
                                        cas[i][n] = '0';
                                        cas[i][j] = '0';
                                        cas[n][i] = '0';
                                        printcastle(*cast, num);
                                        cout << endl;
                                        cout << i + 1 << "->" << n + 1 << endl;
                                        queue(firstmove, i + 1, n + 1);
                                        return;
                                    }
                                    else {
                                        if (cas[i][n] == '5') {
                                            cas[n][n] = '^';
                                            cas[i][n] = '0';
                                            cas[i][j] = '0';
                                            cas[n][i] = '0';
                                            printcastle(*cast, num);
                                            cout << endl;
                                            cout << i + 1 << "->" << n + 1 << endl;
                                            queue(firstmove, i + 1, n + 1);
                                            return;
                                        }
                                        


                                    }
                                }
                            }
                        }

                    
                }
                
            }

        }

}
void castle(char*** cass, int num) {

    char** cas = *cass;
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
            int room;
            room = rand() % 6;
            if (room == 0) {
                cas[i][j] = '0';
                cas[j][i] = '0';
            }
            else {
                if (room == 1) {
                    cas[i][j] = '1';
                    cas[j][i] = '1';
                }
                else {
                    if (room == 2) {
                        cas[i][j] = '2';
                        cas[j][i] = '2';
                    }
                    else {
                        if (room == 3) {
                            cas[i][j] = '3';
                            cas[j][i] = '3';
                        }
                        else {
                            if (room == 4) {
                                cas[i][j] = '4';
                                cas[j][i] = '4';
                            }
                            else {
                                if (room == 5) {
                                    cas[i][j] = '5';
                                    cas[j][i] = '5';
                                }
                            }
                        }
                    }
                }
            }

        }
    }

}


int main(void){
    setlocale(LC_ALL, "Ukr");
    way* firstmove = nullptr;
    int num;
    int room;
    char** cas = nullptr; 
    cout << "Введіть к-сть кімнат у замку: ";
    cin >> num;
    cas = new char* [num];
    for (int i = 0; i < num; i++) {
        cas[i] = new char[num];
    }
    castle(&cas, num);
    printcastle(cas, num);
    prince(&cas, num, room);
    printcastle(cas, num);
    cout << endl;
    for (int i = 0; i < num * num; i++) {
        run(&cas, num,&firstmove);
    }
    moway(&firstmove);
    
        
    

    _getch();
    return 0;
}