#include <iostream>
#include <fstream>
#include <windows.h>

#include<queue>
#include<stack>

using namespace std;

struct Edge {
    COORD begin;
    COORD end;
};

onMap(COORD c, char **mas, int rows, int cols) {
    if (c.X >= cols || c.Y >= rows) return 0;
    if (c.X < 0 || c.Y < 0) return 0;
    if (mas[c.Y][c.X] == '#') return 0;
    return 1;
}

void find_path(char** mas, int rows, int cols) {
    queue<COORD> Queue;
    stack<Edge> Stack;

    char ** visited;
    visited = new char*[rows];
    for (int i = 0; i < rows; i++) {
        visited[i] = new char[cols];
        for (int j = 0; j < cols; j++)
            visited[i][j] = 0;
    }

    HANDLE h = GetStdHandle(STD_OUTPUT_HANDLE);
    COORD B, E;

    // find init coord in grid
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (mas[i][j] == 'B') {
                B.X = j;
                B.Y = i;
            } else if(mas[i][j] == 'E') {
                E.X = j;
                E.Y = i;
            }
        }
    }

    cout << "Begin: (" << B.X << "; " << B.Y << ")" << endl;
    cout << "End  : (" << E.X << "; " << E.Y << ")" << endl;

    Queue.push(B);

    bool flag = false;

    while (!Queue.empty()) {
        COORD c = Queue.front();
        COORD r;
        Edge e;
        e.begin = c;
        Queue.pop();
        visited[c.Y][c.X] = 2;
        if (c.X == E.X && c.Y == E.Y) {
            flag = true;
            break;
        }
        r.X = c.X - 1;
        r.Y = c.Y;
        if (onMap(r, mas, rows, cols) && visited[r.Y][r.X] == 0) {
                Queue.push(r);
                visited[r.Y][r.X] = 1;
                e.end = r;
                Stack.push(e);
        }
        r.X = c.X + 1;
        if (onMap(r, mas, rows, cols) && visited[r.Y][r.X] == 0) {
            Queue.push(r);
            visited[r.Y][r.X] = 1;
            e.end = r;
            Stack.push(e);
        }

        r.X = c.X;
        r.Y = c.Y - 1;
        if (onMap(r, mas, rows, cols) && visited[r.Y][r.X] == 0) {
            Queue.push(r);
            visited[r.Y][r.X] = 1;
            e.end = r;
            Stack.push(e);
        }
        r.Y = c.Y + 1;
        if (onMap(r, mas, rows, cols) && visited[r.Y][r.X] == 0) {
            Queue.push(r);
            visited[r.Y][r.X] = 1;
            e.end = r;
            Stack.push(e);
        }
    }

    if (flag == false) {
        cout << "Path is not found!\n";
        return;
    }

    SetConsoleTextAttribute(h, 0xFC);
    COORD req;
    req.X = E.X; req.Y = E.Y;
    while (!Stack.empty()) {
        Edge e = Stack.top();
        Stack.pop();
        if (e.begin.X == B.X && e.begin.Y == B.Y) break;
        if (req.X == e.end.X && req.Y == e.end.Y) {

            COORD temp = e.begin;
            temp.Y += 2;

            SetConsoleCursorPosition(h, temp);
            req.X = e.begin.X; req.Y = e.begin.Y;
            cout << "*";
        }
    }

}

int main() {
    fstream f;
    f.open("data/file5.txt", ios::in);

    char ** line = new char*[21];
    for (int i = 0; i < 21; ++i) {
        line[i] = new char[21];
    }

    int count = 0;
    while(f.getline(line[count], 21)) {
        cout << line[count] << endl;
        count++;
    }

    f.close();
    find_path(line, 20, 20);

    cin.get();
    return 0;
}