Hypyt

#include <bits/stdc++.h>
using namespace std;
 
class Node
{
public:
    uint8_t x;
    uint8_t y;
    uint64_t depth;
    Node(uint8_t a, uint8_t b, uint64_t d)
    {
        x = a;
        y = b;
        depth = d;
    }
};
 
inline optional<uint64_t> process(
    const Node &current,
    const vector<uint16_t> &opt,
    uint8_t end_x,
    uint8_t end_y,
    vector<vector<uint8_t>> &visited,
    queue<Node> &search_queue,
    unordered_map<uint32_t, uint64_t> &cache,
    uint32_t key_start_part
)
{
    for (uint32_t el : opt)
    {
        uint8_t x = el & 0xFF;
        uint8_t y = (el >> 8) & 0xFF;
        if (current.x == x && current.y == y)
        {
            continue;
        }
        uint64_t value = current.depth + 1;
        if (end_x == x && end_y == y)
        {
            return value;
        }
        if (!visited[y][x])
        {
            uint32_t cache_key = key_start_part | ((uint32_t)x) << 0x10 | ((uint32_t)y) << 0x18;
            cache[cache_key] = value;
            search_queue.push(Node(x, y, value));
            visited[y][x] = true;
        }
    }
    return {};
}
 
optional<uint64_t> path_find(
    const uint8_t x1,
    const uint8_t y1,
    const uint8_t x2,
    const uint8_t y2,
    const vector<vector<uint16_t>> &row_options,
    const vector<vector<uint16_t>> &col_options,
    const uint8_t x_len,
    const uint8_t y_len,
    unordered_map<uint32_t, uint64_t> &cache)
{
    if (x1 == x2 && y1 == y2)
    {
        return 0;
    }
    uint32_t key_start_part = (uint32_t)x1 | ((uint32_t)y1) << 0x8;
    uint32_t cache_key = key_start_part | ((uint32_t)x2) << 0x10 | ((uint32_t)y2) << 0x18;
    if (cache.count(cache_key) > 0)
    {
        return cache[cache_key];
    }
 
    queue<Node> search_queue = {};
    search_queue.push(Node(x1, y1, 0));
 
    vector<vector<uint8_t>> visited(y_len, vector<uint8_t>(x_len, false));
    visited[y1][x1] = true;
 
    while (!search_queue.empty())
    {
        Node current = search_queue.front();
        search_queue.pop();
        auto &r_opt = row_options[current.y];
        auto &c_opt = col_options[current.x];
        optional<uint64_t> res = process(current, r_opt, x2, y2, visited, search_queue, cache, key_start_part);
        if (res.has_value())
        {
            uint64_t value = res.value();
            cache[cache_key] = value;
            return value;
        }
        res = process(current, c_opt, x2, y2, visited, search_queue, cache, key_start_part);
        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<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 (uint8_t y = 0; y < n; y++)
    {
        auto row = grid[y];
        for (uint8_t x = 0; x < m; x++)
        {
            if (row[x])
            {
                uint16_t coords = (uint16_t)x | ((uint16_t)y) << 8;
                options_per_row[y].push_back(coords);
                options_per_col[x].push_back(coords);
            }
        }
    }
 
    unordered_map<uint32_t, uint64_t> cache;
    cache.reserve(0x10000);
    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(x1, y1, x2, y2, 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: TIME LIMIT EXCEEDED

Test 7

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2, 5

Verdict: ACCEPTED

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

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