#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <chrono>

using namespace std;


enum Direction {
  kRight = 0,
  kUp = 1,
  kLeft = 2,
  kDown = 3
};


const char kDirToChar[4] = {'>', '^', '<', 'V'};

char ToChar(Direction d) {
    return kDirToChar[d];
}

class Maze {
public:
    /*
       `map` - map of the labirinth. '#' indicates a wall. 'E' indicates exit.
    */
    Maze(vector<string> map);

    int Width() const;
    int Height() const;
    bool IsExit(int x, int y) const;
    bool IsWall(int x, int y) const;

    /*
       Finds the shortest sequence of moves to get from (x, y) to exit.
       `x` - 0 based column coordinate;
       `y` - 0 based row coordinate;
       (0, 0) is top-left.
    */
    vector<Direction> GetPath(int x, int y) const;

    /*
       Moves turtle from position (x,y) according to `commands`.
       `x` - 0 based column coordinate;
       `y` - 0 based row coordinate;
       returns new position in `x` and `y`.
    */
    void ApplyCommands(int &x, int &y, const vector<Direction> &commands) const;

    ~Maze() = default;

private:
    string _map;
    int _height;
    int _width;
    int _exit;
    int _offset[4];
    vector<int> _prev;
    void Bfs();
};



Maze::Maze(vector<string> map) : _height(map.size()), _width(map[0].size()) {
    for (int i = 0; i < _width + 2; ++i)
        _map += '#';
    for (int i = 0; i < _height; ++i) {
        _map +='#';
        _map += map[i];
        _map += '#';
    }
    for (int i = 0; i < _width + 2; ++i)
        _map += '#';
    _height += 2;
    _width += 2;
    _offset[kRight] = 1;
    _offset[kUp] = -_width;
    _offset[kLeft] = -1;
    _offset[kDown] = _width;
    for (size_t i = 0; i < _map.size(); ++i) {
        if (_map[i] == 'E') {
          _exit = i;
          break;
        }
    }
    Bfs();
}

void Maze::Bfs() {
    _prev.resize(_map.size(), -1);
    queue<int> q;
    q.push(_exit);
    _prev[_exit] = 0;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k) {
            int npos = cur + _offset[k];
            if (_map[npos] != '#' && _prev[npos] == -1) {
                _prev[npos] = k^2;
                q.push(npos);
            }
        }
    }

    cout << "Paths in the maze:\n";
    for (int i = 0; i < _height; ++i) {
        for (int j = 0; j < _width; ++j) {
            int cur = i*_width + j;
            if (_map[cur] == '#') {
                cout << '#';
            } else if (_map[cur] == 'E'){
                cout << 'E';
            } else {
                cout << ToChar(Direction(_prev[cur]));
            }
        }
        cout << "\n";
    }

}

int Maze::Width() const {
    return _width-2;
}

int Maze::Height() const {
    return _height-2;
}


bool Maze::IsExit(int x, int y) const {
    return _map[(y+1)*_width + x + 1] == 'E';
}

bool Maze::IsWall(int x, int y) const {
    return _map[(y+1)*_width + x + 1] == '#';
}


vector<Direction> Maze::GetPath(int x, int y) const {
    int pos = (y+1)*_width + x + 1;
    vector<Direction> commands;
    while (pos != _exit) {
        commands.push_back(Direction(_prev[pos]));
        pos += _offset[_prev[pos]];
    }
    return commands;

}

void Maze::ApplyCommands(int &x, int &y, const vector<Direction> &commands) const {
    int pos = (y+1)*_width + x + 1;
    for (auto &c : commands) {
        if (pos == _exit) break;
        int npos = pos + _offset[c];
        if (_map[npos] != '#')
            pos = npos;
    }
    y = pos / _width - 1;
    x = pos % _width - 1;
}



vector<string> kMaze1 = {
    "....",
    ".##.",
    "..#.",
    "#E#."
};

vector<string> kMaze2 = {
    "....#.....",
    ".##...#.#.",
    "..#####.#.",
    "#E#...#.#.",
    "###.#.....",
};

vector<string> kMaze3 = {
    "...................................................",
    "...................................................",
    "...................................................",
    "...................................................",
    "...................................................",
    "...................................................",
    "...................................................",
    "...................................................",
    "...................................................",
    "...................................................",
    "...................................................",
    "...................................................",
    "...................................................",
    "...................................................",
    "...................................................",
    "...................................................",
    "...................................................",
    "E.................................................."
};



bool Check(const Maze &m, const vector<Direction> commands) {
    for (int x = 0; x < m.Width(); ++x) {
        for (int y = 0; y < m.Height(); ++y) {
            if (m.IsWall(x, y)) continue;
            int nx = x;
            int ny = y;
            m.ApplyCommands(nx, ny, commands);
            if (!m.IsExit(nx, ny)) {
                return false;
            }
        }
    }
    return true;
}



void Algo1(const Maze &m) {
    vector<Direction> commands;
    for (int x = 0; x < m.Width(); ++x) {
        for (int y = 0; y < m.Height(); ++y) {
            if (m.IsWall(x, y)) continue;
            int nx = x;
            int ny = y;

            m.ApplyCommands(nx, ny, commands);
            auto c = m.GetPath(nx, ny);
            commands.insert(commands.end(), c.begin(), c.end());
        }
    }

    if (!Check(m, commands)) {
        cout << "Botva!\n";
    }

}


void Algo2(const Maze &m) {
    vector<Direction> commands;

    vector<pair<int, int>> turtles;
    for (int x = 0; x < m.Width(); ++x) {
        for (int y = 0; y < m.Height(); ++y) {
            if (m.IsWall(x, y)) continue;
            turtles.emplace_back(x, y);
        }
    }

    vector<vector<int>> was(m.Width(), vector<int>(m.Height()));
    int stage = 0;

    while (!turtles.empty()) {
        auto t = turtles[0];
        auto c = m.GetPath(t.first, t.second);
        commands.insert(commands.end(), c.begin(), c.end());

        ++stage;
        size_t last_pos = 0;
        for (size_t i = 1; i < turtles.size(); ++i) {
            m.ApplyCommands(turtles[i].first, turtles[i].second, c);
            if (!m.IsExit(turtles[i].first, turtles[i].second) && was[turtles[i].first][turtles[i].second] < stage) {
                was[turtles[i].first][turtles[i].second] = stage;
                turtles[last_pos++] = turtles[i];
            }
        }
        turtles.resize(last_pos);
    }

    if (!Check(m, commands)) {
        cout << "Botva!\n";
    }
}



int main() {
    Maze m(kMaze3);

    auto start = chrono::high_resolution_clock::now();
    for (int i = 0; i < 1000; ++i) {
        Algo2(m);
    }
    auto stop = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
    cout << "Clever algo took " << duration.count() << "ns\n";

    start = chrono::high_resolution_clock::now();
    for (int i = 0; i < 1000; ++i) {
        Algo1(m);
    }
    stop = chrono::high_resolution_clock::now();
    duration = chrono::duration_cast<chrono::microseconds>(stop - start);
    cout << "Naive algo took " << duration.count() << "ns\n";
    return 0;
}