Hypyt

#include <iostream>
#include <string>
#include <sstream>
#include <memory>
#include <chrono>
#include <vector>
#include <utility>
#include <array>
#include <optional>
#include <queue>
#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;
};

class Board {
public:

    Board(Grid2D<Cell>&& grid)
        : m_grid(std::move(grid)) 
    {
        //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);
                }
            }
        }
    }

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

    int Search() {

        /*if (m_grid.At(m_start.x,m_start.y).isSafe == false || m_grid.At(m_destination.x,m_destination.y).isSafe == false)
        {
            return -1;
        }*/

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

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

        std::fill_n(visitedRows.begin(), m_grid.GetWidth(), 0);
        std::fill_n(visitedCols.begin(), m_grid.GetHeight(), 0);

        std::queue<int> rows;
        std::queue<int> cols;

        //std::queue<uint8_t> nrows;
        //std::queue<uint8_t> ncols;

        rows.push(m_start.x);
        cols.push(m_start.y);

        visitedRows[m_start.x] = 1;
        visitedCols[m_start.y] = 1;
        for (int i = 0; !rows.empty() || !cols.empty(); ++i) {
            //nrows.reserve(m_grid.GetWidth() / 2);
            //ncols.reserve(m_grid.GetHeight() / 2);

            int rSize = rows.size();
            int cSize = cols.size();

            //for (uint8_t row : rows) {
            
            for (int j = 0; j < rSize; ++j) {
                int row = rows.front();
                rows.pop();
                if (visitedRows[row] == 2) continue;
                
                for (int y : m_safeRows[row]) {
                    //std::cout << "(" << row << "," << y << ") ";
                    if (y == m_destination.y && row == m_destination.x) {
                        return i+1;
                    }
                    if (visitedCols[y] != 0) continue;
                    cols.push(y);
                    visitedCols[y] = 1;
                }
                visitedRows[row] = 2;
            }

            for (int j = 0; j < cSize; ++j) {
                int col = cols.front();
                cols.pop();
                if (visitedCols[col] == 2) continue;
                
                for (int x : m_safeCols[col]) {
                    //std::cout << "("<< x << "," << col << ") ";
                    if (x == m_destination.x && col == m_destination.y) {
                        return i+1;
                    }
                    if (visitedRows[x] != 0) continue;
                    rows.push(x);
                    //visitedRows[x] = 1;
                    visitedRows[x] = 1;
                }
                visitedCols[col] = 2;
            }

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

            //for (uint8_t col : cols) {
            

            /*rows = std::move(nrows);
            cols = std::move(ncols);

            nrows = std::queue<uint8_t>();
            ncols = std::queue<uint8_t>();*/
            
        }

        return -1;
    }

public:

    Grid2D<Cell> m_grid;

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

    std::array<std::vector<int>, 250> m_safeRows;
    std::array<std::vector<int>, 250> m_safeCols;

    std::array<int, 250> visitedRows;
    std::array<int, 250> visitedCols;

};

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;
    ops.reserve(numOp);

    for (size_t i = 0; i < numOp; ++i) {
        ops.push_back(ReadOperation());
    }

    //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 (const auto& op : ops) {
        std::cout << board.FindPath(op.first, op.second) << std::endl;
        //std::cout << "1" << 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::milliseconds>(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: ACCEPTED

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5

Verdict: ACCEPTED

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: ACCEPTED

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED