#include <iostream>
#include <cstdlib>
#include <chrono>
#include <thread>
using namespace std;

bool findpath(int row, int col);
void display();

// The maze.
char a[][14] {
    {'X', 'X', 'B', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
    {'X', 'X', ' ', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
    {'X', 'X', ' ', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
    {'X', ' ', ' ', ' ', ' ', ' ', ' ', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
    {'X', 'X', ' ', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
    {'X', 'X', ' ', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
    {' ', ' ', ' ', 'X', 'X', 'X', 'X', ' ', ' ', ' ', ' ', ' ', ' ', 'X'},
    {'X', 'X', ' ', 'X', 'X', 'X', 'X', ' ', 'X', ' ', 'X', 'X', ' ', 'X'},
    {'X', 'X', ' ', ' ', ' ', ' ', ' ', ' ', 'X', ' ', ' ', ' ', ' ', 'X'},
    {'X', 'X', ' ', 'X', 'X', 'X', 'X', 'X', 'X', ' ', 'X', 'X', 'X', 'X'},
    {'X', 'X', ' ', 'X', 'X', 'X', 'X', 'X', 'X', ' ', 'X', 'X', 'X', 'X'},
    {'X', 'X', ' ', 'X', 'X', 'X', 'X', 'X', 'X', ' ', 'X', 'X', 'X', 'X'},
    {'X', 'X', ' ', ' ', 'X', ' ', ' ', ' ', ' ', ' ', 'X', 'X', 'X', 'X'},
    {'X', 'X', 'X', 'X', 'X', ' ', 'X', 'X', ' ', 'X', 'X', 'X', 'X', 'X'},
    {'X', 'X', 'X', 'X', 'X', ' ', 'X', 'X', ' ', 'X', 'X', 'X', 'X', 'X'},
    {'X', 'X', 'X', 'X', 'X', ' ', ' ', ' ', ' ', 'X', 'X', 'X', 'X', 'X'},
    {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', ' ', 'X', 'X', 'X', 'X', 'X'},
    {'X', ' ', ' ', ' ', ' ', ' ', ' ', 'X', ' ', 'X', 'X', 'X', 'X', 'X'},
    {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', ' ', 'X', 'X', 'X', 'X', 'X'},
    {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'E', 'X', 'X', 'X', 'X', 'X'}
};

const int nrows {static_cast<int>(size(a))};
const int ncols {static_cast<int>(size(a[0]))};

void display()
{
    cout << "\033[H\033[J" << flush;   // home cursor, clear screen

    for (int row {0}; row < nrows; ++row)
    {
        for (int col {0}; col < ncols; ++col)
        {
            if (a[row][col] == '.')
            {
                cout << "\033[48;5;9m.\033[0m"; // dot with red background
            }
            else
            {
                cout << a[row][col];
            }
        }
        cout << "\n";
    }

    this_thread::sleep_for(chrono::milliseconds(200));
}

// Return true if there is a path from (row, col) to 'E'.
// Draw the path with dots as we explore and backtrack.
bool findpath(int row, int col)
{
    // Bounds check.
    if (row < 0 || row >= nrows || col < 0 || col >= ncols)
    {
        return false;
    }

    // If at the end, succeed.
    if (a[row][col] == 'E')
    {
        return true;
    }

    // We can step only on blanks or on 'B'.
    if (a[row][col] != ' ' && a[row][col] != 'B')
    {
        return false;
    }

    // Mark current cell (but do not overwrite the 'B').
    const bool isBegin {a[row][col] == 'B'};
    if (!isBegin)
    {
        a[row][col] = '.';
    }
    display();

    struct direction
    {
        int drow;
        int dcol;
    };

    const direction directions[] {
        { 1,  0},   // down
        { 0,  1},   // right
        {-1,  0},   // up
        { 0, -1}    // left
    };

    for (const auto& dir : directions)
    {
        const int r {row + dir.drow};
        const int c {col + dir.dcol};

        if (findpath(r, c))
        {
            return true;
        }
    }

    // Backtrack: erase the dot (but keep the 'B').
    if (!isBegin)
    {
        a[row][col] = ' ';
    }
    display();

    return false;
}

int main()
{
    // Find the 'B'.
    int brow {-1};
    int bcol {-1};

    for (int row {0}; row < nrows; ++row)
    {
        for (int col {0}; col < ncols; ++col)
        {
            if (a[row][col] == 'B')
            {
                brow = row;
                bcol = col;
            }
        }
    }

    if (brow == -1 || bcol == -1)
    {
        cerr << "There was no 'B'.\n";
        return EXIT_FAILURE;
    }

    display();

    if (!findpath(brow, bcol))
    {
        cerr << "There is no path from the 'B' to the 'E'.\n";
        return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}