#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;
}

#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;
}