Hypyt

#include <iostream>
#include <string>
#include <sstream>
#include <memory>
#include <chrono>
#include <vector>
#include <utility>
#include <optional>
#include <set>
#include <unordered_set>
#include <cstdint>

template <typename T>
struct Vector2 {

    Vector2() = default;

    Vector2(T X, T Y)
        : x(X), y(Y) {}

    template <typename X>
    Vector2(const Vector2<X>& other)
        : x(static_cast<T>(other.x)), y(static_cast<T>(other.y)) {}

    T x, y;
};

using Vector2i = Vector2<int>;
using Vector2f = Vector2<float>;

template <typename T>
Vector2<T> operator+(const Vector2<T>& left, const Vector2<T>& right) {
    return Vector2<T>(left.x + right.x, left.y + right.y);
}

template <typename T>
bool operator==(const Vector2<T>& left, const Vector2<T>& right) {
    return left.x == right.x && left.y == right.y;
}

template <typename T>
Vector2<T> operator-(const Vector2<T>& left, const Vector2<T>& right) {
    return Vector2<T>(left.x - right.x, left.y - right.y);
}

template <typename T>
Vector2<T> operator*(const Vector2<T>& left, const Vector2<T>& right) {
    return Vector2<T>(left.x * right.x, left.y * right.y);
}

template <typename T>
Vector2<T> operator/(const Vector2<T>& left, const Vector2<T>& right) {
    return Vector2<T>(left.x / right.x, left.y / right.y);
}

template <typename T>
Vector2<T> Flip(const Vector2<T>& v) {
    return Vector2<T>(v.y, v.x);
}

template <typename T>
class Grid2D {
public:
    Grid2D(size_t width, size_t height, const T& fill = T()) 
        : m_width(width), m_height(height) 
    { m_data.resize(width * height, fill); }
        
    const T& At(size_t x, size_t y) const { return m_data[y * m_width + x]; }

    T& At(size_t x, size_t y) { return m_data[y * m_width + x];  }

    size_t GetWidth() const { return m_width; }

    size_t  GetHeight() const { return m_height; }

private:

    size_t GetIndex(size_t x, size_t y) const { return y * m_width + x; }

    std::vector<T> m_data;
    size_t m_width = 0;
    size_t m_height = 0;
};

struct Cell {
    bool isSafe = false;
    //std::vector<int> horizontalJumps; // offsets
    //std::vector<int> verticalJumps; // offsets
    //bool jumpsCalculated = false;

    //bool isVisited = false;
};

class Board {
public:

    Board(Grid2D<Cell>&& grid)
        : m_grid(std::move(grid)) 
    {
        /*for (size_t y = 0; y < m_grid.GetHeight(); ++y) {
            for (size_t x = 0; x < m_grid.GetWidth(); ++x) {
                CalculatePossibleJumps(Vector2i(x,y));
            }
        }*/
        m_safeRows.resize(m_grid.GetWidth());
        m_safeCols.resize(m_grid.GetHeight());
        for (size_t y = 0; y < m_grid.GetHeight(); ++y) {
            for (size_t x = 0; x < m_grid.GetWidth(); ++x) {
                if (m_grid.At(x,y).isSafe) {
                    m_safeRows[x].push_back(y);
                    m_safeCols[y].push_back(x);
                }
            }
        }
    }

    /*void Print() {
        for (size_t y = 0; y < m_grid.GetHeight(); ++y) {
            for (size_t x = 0; x < m_grid.GetWidth(); ++x) {
                std::cout << (size_t)m_grid.At(x, y).isSafe;
            }
            std::cout << std::endl;
        }

        for (size_t y = 0; y < m_grid.GetHeight(); ++y) {
            for (size_t x = 0; x < m_grid.GetWidth(); ++x) {
                if (m_grid.At(x,y).isSafe == true) {
                    //CalculatePossibleJumps(Vector2i(x, y));
                    std::cout << x << ", " << y << ": H: ";
                    for (int jump : m_grid.At(x,y).horizontalJumps) {
                        std::cout << jump << "; ";
                    }
                    std::cout << "V: ";
                    for (int jump : m_grid.At(x,y).verticalJumps) {
                        std::cout << jump << "; ";
                    }
                    std::cout << std::endl;
                }
            }
            
        }
    }*/

    int FindPath(Vector2i start, Vector2i dest) {
        m_start = start;
        m_destination = dest;
        //auto val = Search(start, 0);
        return Search();
    }

    int Search() {

        if (m_start.x == m_destination.x && m_start.y == m_destination.y) {
            return 0;
        }

        /*for (size_t y = 0; y < m_grid.GetHeight(); ++y) {
            for (size_t x = 0; x < m_grid.GetWidth(); ++x) {
                m_grid.At(x,y).isVisited = false;
            }
        }*/

        //Grid2D<uint8_t> visited(m_grid.GetWidth(), m_grid.GetHeight(), 0);

        std::unordered_set<int> currentsX;
        std::unordered_set<int> currentsY;
        std::unordered_set<int> nextsX;
        std::unordered_set<int> nextsY;

        std::vector<std::vector<uint8_t>> safeRows = m_safeRows;
        std::vector<std::vector<uint8_t>> safeCols = m_safeCols;

        currentsX.insert(m_start.x);
        currentsY.insert(m_start.y);
        //visited.At(m_start.x, m_start.y) = 1;

        for (int i = 0; !currentsX.empty() && !currentsY.empty(); ++i) {

            //std::cout << "ITERATION: " << std::endl;

            for (auto pos : currentsX) {
                //std::cout << "S: " << pos.x << " " << pos.y << std::endl;

                //Cell& cell = m_grid.At(pos.x,pos.y);
                //cell.isVisited = true;
                //visited.At(pos.x,pos.y) = 1;

                //bool t = false;

                for (const auto jump : safeRows[pos]) {
                    Vector2i jumpPos(pos, jump);
                    //if (visited.At(jumpPos.x, jumpPos.y) == 1) continue;
                    if (jumpPos.x == m_destination.x && jumpPos.y == m_destination.y) {
                        return i+1;
                    }
                    //visited.At(jumpPos.x, jumpPos.y) = 1;
                    //std::cout << jumpPos.x << " " << jumpPos.y << std::endl;
                    //nexts.push_back(jumpPos);
                    
                    nextsY.insert(jumpPos.y);
                    
                }

                if (!safeRows[pos].empty()) nextsX.insert(pos);

                //safeCols[pos.y].clear();
                safeRows[pos].clear();

            }

            for (auto pos : currentsY) {

                for (const auto hJump : safeCols[pos]) {
                    Vector2i jumpPos(hJump, pos);
                    //if (visited.At(jumpPos.x, jumpPos.y) == 1) continue;
                    if (jumpPos.x == m_destination.x && jumpPos.y == m_destination.y) {
                        return i+1;
                    }
                    //visited.At(jumpPos.x, jumpPos.y) = 1;
                    //std::cout << jumpPos.x << " " << jumpPos.y << std::endl;
                    //nexts.push_back(jumpPos);
                    nextsX.insert(jumpPos.x);
                    
                
                }
                if (!safeCols[pos].empty()) nextsY.insert(pos);

                safeCols[pos].clear();

            }

            //currents = nexts;
            //nexts.clear();
            currentsX = nextsX;
            currentsY = nextsY;

            nextsX.clear();
            nextsY.clear();

            /*if (currents.size() == 0) {
                break;
            }*/

        }

        //std::cout << "END OF Search" << std::endl;

        return -1;
    }

protected:

    /*void CalculatePossibleJumps(Vector2i pos) {
        m_grid.At(pos.x, pos.y).horizontalJumps.clear();
        m_grid.At(pos.x, pos.y).verticalJumps.clear();
        m_grid.At(pos.x, pos.y).jumpsCalculated = true;

        // Horizontal jumps
        for (size_t x = 1; x < std::max((size_t)pos.x+1, m_grid.GetWidth()-pos.x); ++x) {
            if (pos.x >= x && m_grid.At(pos.x - x, pos.y).isSafe) {
                m_grid.At(pos.x, pos.y).horizontalJumps.push_back(-x);
            } 
            if (pos.x + x < m_grid.GetWidth() && m_grid.At(pos.x+x, pos.y).isSafe) {
                m_grid.At(pos.x, pos.y).horizontalJumps.push_back(x);
            }
        }

        // Vertical jumps
        for (size_t y = 1; y < std::max((size_t)pos.y+1, m_grid.GetHeight()-pos.y); ++y) {
            if (pos.y >= y && m_grid.At(pos.x, pos.y - y).isSafe) {
                m_grid.At(pos.x, pos.y).verticalJumps.push_back(-y);
            }
            if (pos.y + y < m_grid.GetHeight() && m_grid.At(pos.x, pos.y+y).isSafe) {
                m_grid.At(pos.x, pos.y).verticalJumps.push_back(y);
            }
        }
    }*/

public:

    Grid2D<Cell> m_grid;

    Vector2i m_start = Vector2i(0, 0);
    Vector2i m_destination = Vector2i(0, 0);

    std::vector<std::vector<uint8_t>> m_safeRows;
    std::vector<std::vector<uint8_t>> m_safeCols;

};

void ReadParams(
    const std::string& str, 
    size_t* width, 
    size_t* height, 
    size_t* numOp)
{
    std::string token;
    std::stringstream ss(str);

    std::getline(ss, token, ' ');
    *height = std::stoi(token);

    std::getline(ss, token, ' ');
    *width = std::stoi(token);

    std::getline(ss, token, ' ');
    *numOp = std::stoi(token);
}

Grid2D<Cell> ReadBoard(size_t width, size_t height) {
    Grid2D<Cell> grid(width, height);
    for (size_t i = 0; i < height; ++i) {
        std::string line;
        std::getline(std::cin, line);
        for (size_t j = 0; j < width; ++j) {
            if (line[j] == '.') {
                grid.At(j, i).isSafe = true;
            } else {
                grid.At(j, i).isSafe = false;
            }
        }
    }
    return grid;
}

std::pair<Vector2i, Vector2i> ReadOperation() {
    std::string input;
    std::getline(std::cin, input);
    std::stringstream ss(input);

    std::string token;

    Vector2i from, to;

    std::getline(ss, token, ' ');
    from.y = std::stoi(token)-1;

    std::getline(ss, token, ' ');
    from.x = std::stoi(token)-1;

    std::getline(ss, token, ' ');
    to.y = std::stoi(token)-1;

    std::getline(ss, token, ' ');
    to.x = std::stoi(token)-1;

    return std::pair(from, to);
}

int main() {

    

    std::string paramInput;
    std::getline(std::cin, paramInput);

    size_t width, height, numOp;

    ReadParams(paramInput, &width, &height, &numOp);

    Board board(ReadBoard(width, height));

    std::vector<std::pair<Vector2i, Vector2i>> ops;

    for (size_t i = 0; i < numOp; ++i) {
        std::pair<Vector2i, Vector2i> op = ReadOperation();
        ops.push_back(op);
    }

    //std::cout << width << "," << height << "," << numOp << std::endl;

    //board.Print();

    //board.SetPath();

    //std::cout << "Steps: " << board.Search(board.m_start, 0).value() << std::endl;

    auto start = std::chrono::high_resolution_clock::now();
    for (auto op : ops) {
        int v = board.FindPath(op.first, op.second);
        std::cout << v << std::endl;
    }

    //size_t val = board.FindPath(Vector2i(4, 3), Vector2i(3, 1));

    //size_t val2 = board.FindPath(Vector2i(0, 0), Vector2i(2, 0));

    //std::cout << "Steps: " << val  << std::endl;
    //std::cout << "Steps: " << val2 << std::endl;

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

    //std::cout << "duration: " << duration.count() << std::endl;

    return 0;
}

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 6

Group: 2, 5

Verdict: ACCEPTED

Test 7

Group: 2, 5

Verdict: ACCEPTED

Test 8

Group: 2, 5

Verdict: ACCEPTED

Test 9

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 23

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 24

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED