#include <iostream>
#include <vector>
#include <fstream>
#include <iomanip>
#include <queue>

using namespace std;


class MyStack {
private:
    struct help {
        int value;
        help *next;
    };
    help *head;

public:
    MyStack();
    ~MyStack();
    MyStack(const MyStack & Stack);
    void push(int value);
    int pop();
    void del();
    bool isEmpty();
    void printMyStack();
    void clone(MyStack & Stack);
};

MyStack::MyStack() :head(NULL) {
}

MyStack::~MyStack() {
    help *current = head;
    while (current != NULL) {
        current = head->next;
        delete head;
        head = current;
    }
}

MyStack::MyStack(const MyStack & Stack) {
    head = NULL;
    help *current = Stack.head;
    while (current != NULL) {
        push(current->value);
        current = current->next;
    }
}

void MyStack::push(int value) {
    help *current = new help;
    current->value = value;
    current->next = head;
    head = current;

}

int MyStack::pop() {
    if (head == NULL) return -1;
    else {
        int buf = head->value;
        help *current = head;
        head = head->next;
        delete current;
        return buf;
    }

}

void MyStack::del() {
    help *current = head;
    current = head->next;
    delete head;
    head = current;
}

void MyStack::printMyStack() {
    while (head != NULL) {
        cout << pop() << " ";
    }
    cout << endl;
}

bool MyStack::isEmpty() {
    return head ? false : true;
}

void MyStack::clone(MyStack & Stack) {
    while (!Stack.isEmpty()) {
            Stack.pop();
    }
    while (head != NULL) {
        Stack.push(pop());
    }
}

struct Cell {
    int x;
    int y;
    int index;
    int weight;
};

void makeMap(int N, Cell *allCells) {
    ifstream read;
    read.open("map1.txt");
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            read >> allCells[i*N + j].weight;
            allCells[i*N + j].x = i;
            allCells[i*N + j].y = j;
            if (allCells[i*N + j].weight < 0)
                allCells[i*N + j].index = -1;
            else allCells[i*N + j].index = 0;
        }
    }
    read.close();
}

void printMap(int N, Cell *allCells) {
    char free = 249, busy = 254;
    cout << "It's a Map" << endl << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (allCells[i*N + j].weight >= 0) cout << setw(3) << free;
            else cout << setw(3) << busy;
        }
        cout << endl;
    }
    cout << endl;
}

void makeStartPoint(int N, Cell *allCels, int *start) {
    int X, Y;
    bool flag = true;
    while (flag) {
        cout << "Input x and y of the START cell" << endl;
        cin >> X >> Y;
        if ((allCels[(X - 1)*N + (Y - 1)].weight >= 0) && ((X - 1)*N + (Y - 1) >= 0) && ((X - 1)*N + (Y - 1) < N*N)) {
            *start = (X - 1)*N + (Y - 1);
            flag = false;
        }
        else {
            cout << endl << "This cell is closed or is out of map" << endl;
        }
    }
}

void makeFinishPoint(int N, Cell *allCels, int *finish) {
    int X, Y;
    bool flag = true;
    while (flag) {
        cout << endl << "Input x and y of the FINISH cell" << endl;
        cin >> X >> Y;
        if ((allCels[(X - 1)*N + (Y - 1)].weight >= 0) && ((X - 1)*N + (Y - 1) >= 0) && ((X - 1)*N + (Y - 1) < N*N)) {
            *finish = (X - 1)*N + (Y - 1);
            flag = false;
        }
        else {
            cout << endl << "This cell is closed or is out of map" << endl;
        }
    }
}

void wave(int N, struct Cell *allCells, int start, int finish) {
    queue <Cell> myqueue;
    allCells[start].index = 0;
    myqueue.push(allCells[start]);
    while (myqueue.empty() == false) {
        Cell buf = myqueue.front();
        int parameter = buf.x*N + buf.y;
        if (parameter == finish)  break;
        if ((allCells[parameter + 1].index == 0) && ((parameter + 1) < N*N) && (parameter % N != (N - 1)) && (parameter + 1 != start)) {
            allCells[parameter + 1].index = buf.index + 1;
            myqueue.push(allCells[parameter + 1]);
        }
        if ((allCells[parameter - 1].index == 0) && ((parameter - 1) >= 0) && (parameter % N != 0) && (parameter - 1 != start)) {
            allCells[parameter - 1].index = buf.index + 1;
            myqueue.push(allCells[parameter - 1]);
        }
        if ((allCells[parameter - N].index == 0) && ((parameter - N) >= 0) && (parameter - N != start)) {
            allCells[parameter - N].index = buf.index + 1;
            myqueue.push(allCells[parameter - N]);
        }
        if ((allCells[parameter + N].index == 0) && ((parameter + N) < N*N) && (parameter + N != start)) {
            allCells[parameter + N].index = buf.index + 1;
            myqueue.push(allCells[parameter + N]);
        }
        myqueue.pop();
    }
}

void printWave(int N, struct Cell *allCells, int start, int finish) {
    char free = 249, busy = 254;
    cout << "It's your wave" << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (allCells[i*N + j].x*N + allCells[i*N + j].y == start) cout << setw(3) << 'S';
            else {
                if (allCells[i*N + j].x*N + allCells[i*N + j].y == finish) cout << setw(3) << 'F';
                else {
                    if (allCells[i*N + j].index > 0) cout << setw(3) << i*N + j;
                    else {
                        if (allCells[i*N + j].index == 0) cout << setw(3) << free;
                        else {
                            cout << setw(3) << busy;
                        }
                    }
                }
            }
        }
        cout << endl;
    }
    cout << "=============================================" << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (allCells[i*N + j].x*N + allCells[i*N + j].y == start) cout << setw(3) << 'S';
            else {
                if (allCells[i*N + j].x*N + allCells[i*N + j].y == finish) cout << setw(3) << 'F';
                else {
                    if (allCells[i*N + j].index > 0) cout << setw(3) << allCells[i*N + j].index;
                    else {
                        if (allCells[i*N + j].index == 0) cout << setw(3) << free;
                        else {
                            cout << setw(3) << busy;
                        }
                    }
                }
            }
        }
        cout << endl;
    }
    cout << endl;
}

void printAnswer(int N, Cell *allCells, int start, int finish) {
    int current = finish;
    int ans;
    while (current != start) {
        if (allCells[current + 1].index == allCells[current].index - 1) {
            allCells[current].weight = -10;
            current = current + 1;
        }
        else {
            if ((allCells[current - 1].index == allCells[current].index - 1) && (current % 10 != 0)) {
                allCells[current].weight = -10;
                current = current - 1;
            }
            else {
                if (allCells[current - N].index == allCells[current].index - 1) {
                    allCells[current].weight = -10;
                    current = current - N;
                }
                else {
                    if (allCells[current + N].index == allCells[current].index - 1) {
                        allCells[current].weight = -10;
                        current = current + N;
                    }
                }
            }
        }
    }
    cout << "It's your way" << endl << endl;
    char free = 249, busy = 254, way = 253;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (allCells[j*N + i].y*N + allCells[j*N + i].x == start) cout << setw(3) << 'S';
            else {
                if (allCells[j*N + i].y*N + allCells[j*N + i].x == finish) cout << setw(3) << 'F';
                else {
                    if (allCells[j*N + i].weight == -10) cout << setw(3) << way;
                    else {
                        if (allCells[j*N + i].weight < 0) cout << setw(3) << busy;
                        else cout << setw(3) << free;
                    }
                }
            }
        }
        cout << endl;
    }

}

void findWay(int N, Cell *allCells, int start, int finish, MyStack& minWay) {
    MyStack resultWay;
    MyStack way;
    MyStack nodes;

    way.push(finish);
    int current = finish;

    bool flag1 = false;
    bool flag2 = true;
    bool flag3 = true;

    int wayWeight = allCells[finish].weight;
    cout << "Way weight: " << wayWeight << endl;
    int minWayWeight = 0;

    while (flag2) {
        while (current != start) {
            int number = 0;
            int newcurrent = 0;

            if (allCells[current + 1].index == allCells[current].index - 1) { //Справа
                if (flag1) {
                    flag1 = false;
                }
                else {
                    number++;
                    if (number == 1) {
                        wayWeight = wayWeight + allCells[current + 1].weight;
                        cout << wayWeight << " r; ";
                        way.push(current + 1);
                        newcurrent = current + 1;
                    }
                    else {
                        nodes.push(current);
                        nodes.push(wayWeight);
                    }
                }
            }
            if (allCells[current + N].index == allCells[current].index - 1) { //Снизу
                if (flag1) {
                    flag1 = false;
                }
                else {
                    number++;
                    if (number == 1) {
                        wayWeight = wayWeight + allCells[current + N].weight;
                        cout << wayWeight << " d; ";
                        way.push(current + N);
                        newcurrent = current + N;
                    }
                    else {
                        nodes.push(current);
                        nodes.push(wayWeight);
                    }
                }
            }
            if ((allCells[current - 1].index == allCells[current].index - 1) && (current % 10 != 0)) { //Слева
                if (flag1) {
                    flag1 = false;
                }
                else {
                    number++;
                    if (number == 1) {
                        wayWeight = wayWeight + allCells[current - 1].weight;
                        cout << wayWeight << " l; ";
                        way.push(current - 1);
                        newcurrent = current - 1;
                    }
                    else {
                        nodes.push(current);
                        nodes.push(wayWeight);
                    }
                }
            }
            if (allCells[current - N].index == allCells[current].index - 1) { //Сверху
                if (flag1) {
                    flag1 = false;
                }
                else {
                    number++;
                    if (number == 1) {
                        wayWeight = wayWeight + allCells[current - N].weight;
                        cout << wayWeight << " u; ";
                        way.push(current - N);
                        newcurrent = current - N;
                    }
                    else {
                        nodes.push(current);
                        nodes.push(wayWeight);
                    }
                }
            }
            current = newcurrent;
        }
        cout << endl;

        if (flag3) {
            flag3 = false;
            minWayWeight = wayWeight;
            cout << endl;
            cout << "== == == == ==" << endl;
            cout << "Minimum way now: " << minWayWeight << endl;
            MyStack minWay(way);
            minWay.clone(resultWay);
            cout << "== == == == ==" << endl;
            cout << endl;
        }
        else {
            if (wayWeight < minWayWeight) {
                minWayWeight = wayWeight;
                cout << endl;
                cout << "== == == == ==" << endl;
                cout << "Minimum way now!!!: " << minWayWeight << endl;
                MyStack minWay(way);
                minWay.clone(resultWay);
                cout << "== == == == ==" << endl;
                cout << endl;
            }
        }

        if (!nodes.isEmpty()) {
            cout << "Change node in way ";
            wayWeight = nodes.pop();
            current = nodes.pop();
            int p = allCells[current].index - allCells[start].index;
            for (int i = 0; i < p; i++) {
                way.del();
            }
            flag1 = true;
        }
        else {
            flag2 = false;
        }
    }
    resultWay.clone(minWay);
}


int main() {
    const int N = 10;
    int start, finish;
    Cell *allCells = new Cell[N*N];

    makeMap(N, allCells);
    printMap(N, allCells);
    makeStartPoint(N, allCells, &start);
    makeFinishPoint(N, allCells, &finish);
    wave(N, allCells, start, finish);
    printWave(N, allCells, start, finish);

    MyStack minWay;
    findWay(N, allCells, start, finish, minWay);
    minWay.printMyStack();
    return 0;
}