Hypyt

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

class Node
{
public:
    pair<uint8_t, uint8_t> coords;
    uint64_t depth;
    Node(pair<uint8_t, uint8_t> p, uint64_t d)
    {
        coords = p;
        depth = d;
    }
};

optional<uint64_t> process(
    Node &current,
    vector<pair<uint8_t, uint8_t>> &opt,
    pair<uint8_t, uint8_t> &end,
    vector<vector<bool>> &visited,
    queue<Node> &search_queue)
{
    for (pair<uint8_t, uint8_t> el : opt)
    {
        if (el == current.coords)
        {
            continue;
        }
        if (el == end)
        {
            return current.depth + 1;
        }
        if (!visited[el.second][el.first])
        {
            search_queue.push(Node(el, current.depth + 1));
            visited[el.second][el.first] = true;
        }
    }
    return {};
}

optional<uint64_t> path_find(
    pair<uint8_t, uint8_t> &start,
    pair<uint8_t, uint8_t> &end,
    vector<vector<pair<uint8_t, uint8_t>>> &row_options,
    vector<vector<pair<uint8_t, uint8_t>>> &col_options,
    uint8_t x_len,
    uint8_t y_len,
    unordered_map<uint32_t, uint64_t> &cache)
{
    if (start == end)
    {
        return 0;
    }
    uint32_t cache_key = (uint32_t)start.first | ((uint32_t)start.second) << 0x8 | ((uint32_t)end.first) << 0x10 | ((uint32_t)end.second) << 0x18;
    if (cache.count(cache_key) > 0)
    {
        return cache[cache_key];
    }

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

    vector<vector<bool>> visited(y_len, vector<bool>(x_len, false));
    visited[start.second][start.first] = true;

    while (!search_queue.empty())
    {
        Node current = search_queue.front();
        search_queue.pop();
        auto &r_opt = row_options[current.coords.second];
        auto &c_opt = col_options[current.coords.first];
        optional<uint64_t> res = process(current, r_opt, end, visited, search_queue);
        if (res.has_value())
        {
            uint64_t value = res.value();
            cache[cache_key] = value;
            return value;
        }
        res = process(current, c_opt, end, visited, search_queue);
        if (res.has_value())
        {
            uint64_t value = res.value();
            cache[cache_key] = value;
            return value;
        }
    }

    return {};
}

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

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

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

    vector<vector<pair<uint8_t, uint8_t>>> options_per_row(n, vector<pair<uint8_t, uint8_t>>());
    vector<vector<pair<uint8_t, uint8_t>>> options_per_col(m, vector<pair<uint8_t, uint8_t>>());
    for (uint8_t y = 0; y < n; y++)
    {
        auto row = grid[y];
        for (uint8_t x = 0; x < m; x++)
        {
            if (row[x])
            {
                pair<uint8_t, uint8_t> coords = {x, y};
                options_per_row[y].push_back(coords);
                options_per_col[x].push_back(coords);
            }
        }
    }

    unordered_map<uint32_t, uint64_t> cache;
    for (uint32_t i = 0; i < q; i++)
    {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        y1--;
        x1--;
        y2--;
        x2--;
        pair<uint8_t, uint8_t> start = {x1, y1};
        pair<uint8_t, uint8_t> end = {x2, y2};
        optional<uint64_t> res = path_find(start, end, options_per_row, options_per_col, 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: 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: ACCEPTED

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