Hypyt

#include <bits/stdc++.h>
using namespace std;

class Node
{
public:
    uint16_t id;
    uint64_t depth;
    Node(uint16_t i, uint64_t d)
    {
        id = i;
        depth = d;
    }
};

uint16_t id(const uint8_t x, const uint8_t y, const uint8_t max_y)
{
    return x * max_y + y;
}

optional<uint64_t> path_find(
    uint16_t start_i,
    uint16_t end_i,
    const vector<vector<uint16_t>> &opts,
    uint8_t x_len,
    uint8_t y_len,
    unordered_map<uint32_t, uint64_t> &cache)
{
    if (start_i == end_i)
    {
        return 0;
    }
    uint32_t cache_key = (uint32_t)start_i | ((uint32_t)end_i << 0x10);
    if (cache.find(cache_key) != cache.end())
    {
        return cache[cache_key];
    }

    queue<Node> search_queue = {};
    search_queue.push(Node(start_i, 0));

    vector<uint8_t> visited(x_len * y_len, false);
    visited[start_i] = true;

    while (!search_queue.empty())
    {
        Node current = search_queue.front();
        search_queue.pop();
        auto opt = opts[current.id];
        for (uint32_t el : opt)
        {
            if (current.id == el)
            {
                continue;
            }
            uint64_t value = current.depth + 1;
            if (el == end_i)
            {
                cache[cache_key] = value;
                return value;
            }
            if (!visited[el])
            {
                search_queue.push(Node(el, value));
                uint32_t cache_key = (uint32_t)start_i | ((uint32_t)el << 0x10);
                cache[cache_key] = value;
                visited[el] = true;
            }
        }
    }

    return {};
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    uint32_t q;
    cin >> n >> m >> q;

    vector<vector<uint8_t>> grid(n, vector<uint8_t>(m, false));
    string line;
    for (uint8_t y = 0; y < n; y++)
    {
        cin >> line;
        for (uint8_t x = 0; x < m; x++)
        {
            grid[y][x] = line[x] == '.';
        }
        line.clear();
    }

    vector<vector<uint16_t>> options_per_row(n, vector<uint16_t>());
    options_per_row.reserve(n * m);
    vector<vector<uint16_t>> options_per_col(m, vector<uint16_t>());
    options_per_col.reserve(n * m);
    for (uint16_t y = 0; y < n; y++)
    {
        auto row = grid[y];
        for (uint16_t x = 0; x < m; x++)
        {
            if (row[x])
            {
                uint16_t i = id(x, y, n);
                options_per_row[y].push_back(i);
                options_per_col[x].push_back(i);
            }
        }
    }
    vector<vector<uint16_t>> options(n * m, vector<uint16_t>());
    options.reserve(n * n * m * m);
    for (uint16_t y = 0; y < n; y++)
    {
        for (uint16_t x = 0; x < m; x++)
        {
            uint16_t i = id(x, y, n);
            options[i].reserve(options_per_col[x].size() + options_per_row[y].size());
            for (auto opts : {&options_per_col[x], &options_per_row[y]})
            {
                options[i].insert(options[i].end(), opts->begin(), opts->end());
            }
        }
    }

    unordered_map<uint32_t, uint64_t> cache;
    cache.reserve(0x1000000);
    for (uint32_t i = 0; i < q; i++)
    {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        y1--;
        x1--;
        y2--;
        x2--;
        optional<uint64_t> res = path_find(id(x1, y1, n), id(x2, y2, n), options, m, n, cache);
        if (res.has_value())
        {
            cout << res.value() << '\n';
        }
        else
        {
            cout << "-1\n";
        }
    }
}

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: RUNTIME ERROR

terminate called after throwing an instance of 'std::length_error'
  what():  vector::reserve

Test 7

Group: 2, 5

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::length_error'
  what():  vector::reserve

Test 8

Group: 2, 5

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::length_error'
  what():  vector::reserve

Test 9

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

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: RUNTIME ERROR

terminate called after throwing an instance of 'std::length_error'
  what():  vector::reserve

Test 16

Group: 5

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::length_error'
  what():  vector::reserve

Test 17

Group: 5

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::length_error'
  what():  vector::reserve

Test 18

Group: 5

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::length_error'
  what():  vector::reserve

Test 19

Group: 5

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::length_error'
  what():  vector::reserve

Test 20

Group: 5

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::length_error'
  what():  vector::reserve

Test 21

Group: 5

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::length_error'
  what():  vector::reserve

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: RUNTIME ERROR

terminate called after throwing an instance of 'std::length_error'
  what():  vector::reserve

Test 27

Group: 5

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::length_error'
  what():  vector::reserve