Vasya project

// ConsoleApplication1.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
//

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <fstream>
#include <optional>

using namespace std;

struct cell
{
    int r, c;
    bool operator<(const cell& rhs)const
    {
        return r < rhs.r || (r == rhs.r && c < rhs.c);
    }
    cell operator+(cell rhs)
    {
        return { r + rhs.r,c + rhs.c };
    }
    bool is_inside(int rows, int cols)
    {
        return 0 <= r && r < rows && 0 <= c && c < cols;
    }
};

static vector<cell> directions{ {0,1},{1,0},{-1,0},{0,-1} };
static int infty = 1'000'000;

class labyrinth
{
    vector<vector<char>> m;
public:
    labyrinth(size_t rows, size_t cols)
    {
        m.assign(rows, vector<char>(cols, '.'));
    }
    vector<char>& operator[](int row)
    {
        return m[row];
    }
    const vector<char>& operator[](int row) const
    {
        return m[row];
    }
    char& operator()(const cell& C)
    {
        return m[C.r][C.c];
    }
    const char& operator()(const cell& C) const
    {
        return m[C.r][C.c];
    }
    int rows() const
    {
        return m.size();
    }
    int cols() const
    {
        return m.size() == 0 ? 0 : m[0].size();
    }
};

labyrinth get_lab_from_stream(istream& inp)
{
    int rows, cols;
    inp >> rows >> cols;
    labyrinth lab(rows, cols);
    for (size_t i = 0; i < rows; i++)
    {
        for (size_t j = 0; j < cols; j++)
        {
            inp >> lab[lab.rows() - i - 1][j];
        }
    }
    return lab;
}

void BFS(const labyrinth& lab, cell s, map<cell, double>& d, map<cell, cell>& p, bool requires_init)
{
    if (requires_init)
    {
        for (int i = 0; i < lab.rows(); i++)
            for (int j = 0; j < lab.cols(); j++)
            {
                d[{i, j}] = infty; //lab.rows() * lab.cols();
                p[{i, j}] = { -1,-1 };
            }
    }
    d[s] = 0;
    queue<cell> Q;
    Q.push(s);
    while (Q.size())
    {
        auto u = Q.front();
        Q.pop();
        for (auto dir : directions)
        {
            auto v = u + dir;
            if (!v.is_inside(lab.rows(), lab.cols())) continue;
            if (lab(v) != '#' && d[v] > d[u] + 1)
            {
                d[v] = d[u] + 1;
                p[v] = u;
                Q.push(v);
            }
        }
    }
}

void BFS(const labyrinth& lab, const vector<cell>& s, map<cell, double>& d, map<cell, cell>& p, bool requires_init)
{
    if (requires_init)
    {
        for (int i = 0; i < lab.rows(); i++)
            for (int j = 0; j < lab.cols(); j++)
            {
                d[{i, j}] = infty; //lab.rows() * lab.cols();
                p[{i, j}] = { -1,-1 };
            }
    }
    queue<cell> Q;
    for (auto u : s)
    {
        d[u] = 0;
        Q.push(u);
    }
    while (Q.size())
    {
        auto u = Q.front();
        Q.pop();
        for (auto dir : directions)
        {
            auto v = u + dir;
            if (!v.is_inside(lab.rows(), lab.cols())) continue;
            if (lab(v) != '#' && d[v] > d[u] + 1)
            {
                d[v] = d[u] + 1;
                p[v] = u;
                Q.push(v);
            }
        }
    }
}

//Вася и потоп
//flood_speed - интервал затопления очередного уровня
void BFS2(const labyrinth& lab, cell s, double flood_speed, map<cell, double>& d, map<cell, cell>& p, bool requires_init)
{
    if (requires_init)
    {
        for (int i = 0; i < lab.rows(); i++)
            for (int j = 0; j < lab.cols(); j++)
            {
                d[{i, j}] = infty; //lab.rows() * lab.cols();
                p[{i, j}] = { -1,-1 };
            }
    }
    d[s] = 0;
    queue<cell> Q;
    Q.push(s);
    while (Q.size())
    {
        auto u = Q.front();
        Q.pop();
        for (auto dir : directions)
        {
            auto v = u + dir;
            if (!v.is_inside(lab.rows(), lab.cols())) continue;
            if (lab(v) != '#' && d[v] > d[u] + 1 && v.r >= floor(d[u] / flood_speed))
            {
                d[v] = d[u] + 1;
                p[v] = u;
                Q.push(v);
            }
        }
    }
}

//Вася и потоп
//fire_speed - интервал распространения огня
void BFS3(const labyrinth& lab, cell s, double fire_speed, map<cell, double>& d, map<cell, cell>& p, bool requires_init)
{
    if (requires_init)
    {
        for (int i = 0; i < lab.rows(); i++)
            for (int j = 0; j < lab.cols(); j++)
            {
                d[{i, j}] = infty; //lab.rows() * lab.cols();
                p[{i, j}] = { -1,-1 };
            }
    }
    vector<cell> fire_cells;
    for (int i = 0; i < lab.rows(); i++)
        for (int j = 0; j < lab.cols(); j++)
        {
            if (lab[i][j] == '*')
                fire_cells.push_back({ i,j });
        }
    map<cell, double> dfire;
    map<cell, cell> pfire;
    BFS(lab, fire_cells, dfire, pfire, true);

    d[s] = 0;
    queue<cell> Q;
    Q.push(s);
    while (Q.size())
    {
        auto u = Q.front();
        Q.pop();
        for (auto dir : directions)
        {
            auto v = u + dir;
            if (!v.is_inside(lab.rows(), lab.cols())) continue;
            if (lab(v) != '#' && d[v] == infty && dfire[v] * fire_speed > d[u])
            {
                d[v] = d[u] + 1;
                p[v] = u;
                Q.push(v);
            }
        }
    }
}

//Вася и слизь
//slime_time - время для перехода из клетки со слизью
void BFS4(const labyrinth& lab, cell s, double slime_time, map<cell, double>& d, map<cell, cell>& p, bool requires_init)
{
    if (requires_init)
    {
        for (int i = 0; i < lab.rows(); i++)
            for (int j = 0; j < lab.cols(); j++)
            {
                d[{i, j}] = infty; //lab.rows() * lab.cols();
                p[{i, j}] = { -1,-1 };
            }
    }
    d[s] = 0;
    queue<cell> Q;
    Q.push(s);
    while (Q.size())
    {
        auto u = Q.front();
        Q.pop();
        for (auto dir : directions)
        {
            auto v = u + dir;
            if (!v.is_inside(lab.rows(), lab.cols())) continue;
            if (lab(v) != '#' && (lab(u) != '~' ? d[v] > d[u] + 1 : d[v] > d[u] + slime_time))
            {
                d[v] = d[u] + (lab(u) != '~' ? 1.0 : slime_time);
                p[v] = u;
                Q.push(v);
            }
        }
    }
}

//алгоритм поиска в ширину для имитации растекания слизи
void BFS_slime(const labyrinth& lab, const vector<cell>& s, map<cell, double>& d, map<cell, cell>& p, bool requires_init)
{
    if (requires_init)
    {
        for (int i = 0; i < lab.rows(); i++)
            for (int j = 0; j < lab.cols(); j++)
            {
                d[{i, j}] = infty; //lab.rows() * lab.cols();
                p[{i, j}] = { -1,-1 };
            }
    }
    queue<cell> Q;
    for (auto u : s)
    {
        d[u] = 0;
        Q.push(u);
    }
    while (Q.size())
    {
        auto u = Q.front();
        Q.pop();
        vector<cell> _directions;
        if (!(u + cell{ -1, 0 }).is_inside(lab.rows(), lab.cols()) || lab(u + cell{ -1, 0 }) != '#')
            _directions.assign({ { 0,-1 },{0,1} });
        else
            _directions.assign({ { -1,0 } });
        for (auto dir : _directions)
        {
            auto v = u + dir;
            if (!v.is_inside(lab.rows(), lab.cols())) continue;
            if (lab(v) != '#' && d[v] > d[u] + 1)
            {
                d[v] = d[u] + 1;
                p[v] = u;
                Q.push(v);
            }
        }
    }
}

//Вася и слизь потекла
//slime_time - время для перехода из клетки со слизью
//slime_speed - время для растекания слизи на соседнюю клетку
//слизь либо стекает вниз, если под ней свободная клетка, либо растекается вправо и влево
void BFS5(const labyrinth& lab, cell s, double slime_time, double slime_speed, map<cell, double>& d, map<cell, cell>& p, bool requires_init)
{
    if (requires_init)
    {
        for (int i = 0; i < lab.rows(); i++)
            for (int j = 0; j < lab.cols(); j++)
            {
                d[{i, j}] = infty; //lab.rows() * lab.cols();
                p[{i, j}] = { -1,-1 };
            }
    }
    vector<cell> slime_cells;
    for (int i = 0; i < lab.rows(); i++)
        for (int j = 0; j < lab.cols(); j++)
            if (lab[i][j] == '~')
                slime_cells.push_back({ i,j });
    map<cell, double> dslime;
    map<cell, cell> pslime;
    BFS_slime(lab, slime_cells, dslime, pslime, true);

    d[s] = 0;
    queue<cell> Q;
    Q.push(s);
    while (Q.size())
    {
        auto u = Q.front();
        Q.pop();
        for (auto dir : directions)
        {
            auto v = u + dir;
            if (!v.is_inside(lab.rows(), lab.cols())) continue;
            if (lab(v) != '#' && (dslime[u] * slime_speed > d[u] ? d[v] > d[u] + 1 : d[v] > d[u] + slime_time))
            {
                d[v] = d[u] + (dslime[u] * slime_speed > d[u] ? 1.0 : slime_time);
                p[v] = u;
                Q.push(v);
            }
        }
    }
}

//Вася и 1 динамамит

//Специальная версия поиска в ширину, которая заходит в стены, но не выходит из них
void BFS_wall(const labyrinth& lab, cell s, map<cell, double>& d, map<cell, cell>& p, bool requires_init)
{
    if (requires_init)
    {
        for (int i = 0; i < lab.rows(); i++)
            for (int j = 0; j < lab.cols(); j++)
            {
                d[{i, j}] = infty; //lab.rows() * lab.cols();
                p[{i, j}] = { -1,-1 };
            }
    }
    queue<cell> Q;
    d[s] = 0;
    Q.push(s);
    while (Q.size())
    {
        auto u = Q.front();
        Q.pop();
        for (auto dir : directions)
        {
            auto v = u + dir;
            if (!v.is_inside(lab.rows(), lab.cols())) continue;
            if (d[v] > d[u] + 1)
            {
                d[v] = d[u] + 1;
                p[v] = u;
                if(lab(v) != '#')
                    Q.push(v);
            }
        }
    }
}

std::optional<cell> optimal_cell_to_explode(const labyrinth& lab, cell start, cell finish)
{
    map<cell, double> ds, df;
    map<cell,cell> ps, pf;
    BFS_wall(lab, start, ds, ps, true);
    BFS_wall(lab, finish, df, pf, true);
    cell opt=start;
    double optlength = ds[start]+df[start];
    for (int i = 0; i < lab.rows(); i++)
    {
        for (int j = 0; j < lab.cols(); j++)
        {
            if (optlength > ds[{i, j}] + df[{i, j}])
            {
                optlength = ds[{i, j}] + df[{i, j}];
                opt = { i,j };
            }
        }
    }
    //std::cout << optlength << std::endl;
    //std::cout << ds[{7, 6}] << " " << df[{7, 6}] << std::endl;
    if (optlength == infty)
        return std::nullopt;
    return opt;
}

vector<cell> get_path(map<cell, double>& d, map<cell, cell>& p, cell dest)
{
    vector<cell> res;
    if (d[dest] == infty)
        return res;
    res.push_back(dest);
    while (d[res.back()] > 0)
        res.push_back(p[res.back()]);
    reverse(begin(res), end(res));
    return res;
}

int main()
{
    fstream inp("lab.txt");
    auto lab = get_lab_from_stream(inp);
    map<cell, double> d;
    map<cell, cell> p;
    auto res=optimal_cell_to_explode(lab, { 0,0 }, {11,11});
    if (res)
        std::cout << res.value().r << " " << res.value().c << std::endl;
    else
        std::cout << "No wall to explode\n";

    //std::cout << d[{ lab.rows() - 1, lab.cols() - 1 }] << std::endl;

    //auto path = get_path(d, p, { lab.rows() - 1,lab.cols() - 1 });
    //for (auto v : path)
    //    std::cout << '(' << v.r << ',' << v.c << ") ";

    std::cout << "\n";
}

// Запуск программы: CTRL+F5 или меню "Отладка" > "Запуск без отладки"
// Отладка программы: F5 или меню "Отладка" > "Запустить отладку"

// Советы по началу работы
//   1. В окне обозревателя решений можно добавлять файлы и управлять ими.
//   2. В окне Team Explorer можно подключиться к системе управления версиями.
//   3. В окне "Выходные данные" можно просматривать выходные данные сборки и другие сообщения.
//   4. В окне "Список ошибок" можно просматривать ошибки.
//   5. Последовательно выберите пункты меню "Проект" > "Добавить новый элемент", чтобы создать файлы кода, или "Проект" > "Добавить существующий элемент", чтобы добавить в проект существующие файлы кода.
//   6. Чтобы снова открыть этот проект позже, выберите пункты меню "Файл" > "Открыть" > "Проект" и выберите SLN-файл.
/*
12 12
...#..#.....
........###.
.###.##.#.##
...###..#...
...#.#.##.#.
#.##.#....#.
..#..#..###.
.##.........
..#..######.
#.........#.
#.#####.##..
......#...#.
*/