Задачи про Васю

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <fstream>
#include <numeric>
#include <functional>

using graph = std::vector<std::vector<int>>;
using std::vector;

//базовый поиск в ширину
void BFS(const graph& g, int s, vector<int>& d, vector<int>& p, bool need_init = true)
{
    int infty = g.size();
    if (need_init)
    {
        d.assign(g.size(), infty);
        p.assign(g.size(), -1);
    }
    d[s] = 0;
    std::queue<int> Q;
    Q.push(s);
    while (Q.size())
    {
        auto u = Q.front();
        Q.pop();
        for (auto v : g[u])
        {
            if (d[v] == infty)
            {
                d[v] = d[u] + 1;
                p[v] = u;
                Q.push(v);
            }
        }
    }
}

vector<int> vertices_from_shortest_path(const graph& g, int a, int b)
{
    int infty = g.size();
    vector<int> da, db, p;
    BFS(g, a, da, p, true);
    BFS(g, b, db, p, true);
    vector<int> res;
    for (size_t u = 0; u < g.size(); u++)
    {
        if (da[u] + db[u] == da[b])
            res.push_back(u);
    }
    return res;
}

//https://pastebin.com/6MDNTGUj

struct cell { int r, c; };
const cell nullcell = cell{ -1,-1 };

template <typename T>
class table
{
public:
    vector<vector<T>> m;
    table(size_t _rows = 0, size_t _cols = 0, T val = T()) { m.assign(_rows, vector<T>(_cols, val)); }
    size_t rows()const { return m.size(); }
    size_t cols()const { return m.size() ? m[0].size() : 0; }
    T operator[](cell c)const { return m[c.r][c.c]; }
    T& operator[](cell c) { return m[c.r][c.c]; }
};

using labyrinth = table<char>;

labyrinth get_labyrinth_from_stream(std::istream& inp)
{
    int row, col;
    inp >> row >> col;
    labyrinth lab(row, col);
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < col; j++)
        {
            char c;
            inp >> c;
            lab[{row - i - 1, j}] = c;
        }
    }
    return lab;
}

vector<cell> adjoint_cells(const labyrinth& lab, cell c)
{
    vector<cell> res;
    for (int i = -1; i <= 1; ++i)
    {
        if (i != 0 && i + c.r >= 0 && i + c.r < lab.rows())
            res.push_back({ i + c.r,c.c });
        if (i != 0 && i + c.c >= 0 && i + c.c < lab.cols())
            res.push_back({ c.r,i + c.c });
    }
    return res;
}

void BFSlab(const labyrinth& lab, const vector<cell>& s, table<int>& d, table<cell>& p,
    std::function<vector<cell>(const labyrinth&,cell)> adj_cells = adjoint_cells)
{
    int infty = lab.rows() * lab.cols();
    d = table<int>(lab.rows(), lab.cols(), infty);
    p = table<cell>(lab.rows(), lab.cols(), nullcell);
    std::queue<cell> Q;
    for (auto c : s)
    {
        d[c] = 0;
        Q.push(c);
    }
    while (Q.size())
    {
        auto c = Q.front();
        Q.pop();
        for (auto v : adj_cells(lab, c))
        {
            if ((lab[v]) != '#' && (d[v]) == infty)
            {
                d[v] = d[c] + 1;
                p[v] = c;
                Q.push(v);
            }
        }
    }
}

void BFSlab_fire(const labyrinth& lab, cell s, double fire_speed, table<int>& d, table<cell>& p)
{
    int infty = lab.rows() * lab.cols();
    d = table<int>(lab.rows(), lab.cols(), infty);
    p = table<cell>(lab.rows(), lab.cols(), nullcell);

    table<int> dfire;
    table<cell> pfire;
    vector<cell> firecells;
    for (int i = 0; i < lab.rows(); ++i)
        for (int j = 0; j < lab.cols(); j++)
            if (lab[{i, j}] == 'F') firecells.push_back({ i, j });
    BFSlab(lab, firecells, dfire, pfire);

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

vector<cell> adjoint_cells_for_slime(const labyrinth& lab, cell c)
{
    if (c.r > 0 && lab[{c.r - 1, c.c}] != '#')
        return { {c.r - 1, c.c} };
    vector<cell> res;
    if (c.c > 0) res.push_back({ c.r,c.c - 1 });
    if (c.c < lab.cols()-1) res.push_back({ c.r,c.c + 1 });
    return res;
}

void BFSlab_slime(const labyrinth& lab, cell s, double slime_speed, double slime_slowdown, table<int>& d, table<cell>& p)
{
    int infty = lab.rows() * lab.cols()*std::max(1.0,slime_slowdown);
    d = table<int>(lab.rows(), lab.cols(), infty);
    p = table<cell>(lab.rows(), lab.cols(), nullcell);

    table<int> dslime;
    table<cell> pslime;
    vector<cell> slimecells;
    for (int i = 0; i < lab.rows(); ++i)
        for (int j = 0; j < lab.cols(); j++)
            if (lab[{i, j}] == 'S') slimecells.push_back({ i, j });
    BFSlab(lab, slimecells, dslime, pslime,adjoint_cells_for_slime);

    d[s] = 0;
    std::queue<cell> Q;
    Q.push(s);
    while (Q.size())
    {
        auto c = Q.front();
        Q.pop();
        for (auto v : adjoint_cells(lab, c))
        {
            double time_for_step = d[c]>=dslime[c]*slime_speed ? slime_slowdown : 1.0;
            if (lab[v] == '#') continue;
            if (d[v] == infty || d[v] > d[c]+time_for_step)
            {
                d[v] = d[c] + time_for_step;
                p[v] = c;
                Q.push(v);
            }
        }
    }
}

void BFSlab_dynamite(const labyrinth& lab, const vector<cell>& s, int D,
    table<vector<int>>& d, table<vector<std::pair<cell,int>>>& p,
    std::function<vector<cell>(const labyrinth&, cell)> adj_cells = adjoint_cells)
{
    int infty = lab.rows() * lab.cols();
    d = table<vector<int>>(lab.rows(), lab.cols(), vector<int>(D+1,infty));
    p = table<vector<std::pair<cell, int>>>(lab.rows(), lab.cols(),
        vector<std::pair<cell, int>>(D + 1, { nullcell,0 }));
    std::queue<std::pair<cell,int>> Q;
    for (auto c : s)
    {
        d[c][D] = 0;
        Q.push({ c,D });
    }
    while (Q.size())
    {
        auto [c,r] = Q.front();
        Q.pop();
        for (auto v : adj_cells(lab, c))
        {
            if (lab[v] == '#' && r > 0 && d[v][r - 1] > d[c][r] + 1)
            {
                d[v][r - 1] = d[c][r] + 1;
                Q.push({ v,r - 1 });
                p[v][r - 1] = { c,r };
            }
            else if ((lab[v]) != '#' && d[v][r] > d[c][r] + 1)
            {
                d[v][r] = d[c][r] + 1;
                p[v][r] = { c,r };
                Q.push({ v,r });
            }
        }
    }
}


int main()
{
    std::ifstream inp("lab.txt");
    auto lab = get_labyrinth_from_stream(inp);
    //table<int> d;
    //table<cell> p;
    //BFSlab(lab, { { 0,0 } }, d, p);
    //BFSlab_fire(lab, { 0,0 }, 1.8, d, p);
    //BFSlab_slime(lab, { 0,0 }, 2.0, 5.0, d, p);
    //std::cout << (d[{ 11, 11 }]) << std::endl;
    //cell current = { 11,11 };
    //while (current.r != -1)
    //{
    //    std::cout << current.r << ',' << current.c << "  ";
    //    current = p[current];
    //}
    //std::wcout << std::endl;
    table<vector<int>> d;
    table<vector<std::pair<cell, int>>> p;
    BFSlab_dynamite(lab, { {0,0} }, 1, d, p);
    std::cout << d[{ 11, 11 }][1] << std::endl;
    cell current = { 11,11 };
    int dynamite = 1;
    while (current.r != -1)
    {
        std::cout << current.r << ',' << current.c << "("<<dynamite<<")  ";
        auto cd = p[current][dynamite];
        current = cd.first;
        dynamite = cd.second;
    }
    std::wcout << std::endl;
}

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

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

https://pastebin.com/z1sehyKw

12 12
...#..#.....
........###.
.###.##.#.##
...###..#...
...#.#.##.#.
#.##.#....#F
..#..#..###.
.##........F
..#..######.
#........F#.
#.#####.##..
......#...#.
*/