Hypyt

// TODO:
// optimize!
// store some results of previous calculations somehow
// board is only 250x250, so caching a lot is fine

#include <iostream>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <queue>

#define is_movable(char) (char == '.')
#define Queue std::priority_queue<AStarNode, std::vector<AStarNode>, Compare>


typedef unsigned int uint;
typedef unsigned char uc;

// space optimization: one byte per pos (max: 250)
typedef struct vec2 {
    unsigned char x;
    unsigned char y;
} vec2;

typedef struct vec4 {
    vec2 first;
    vec2 second;
} vec4;

inline unsigned short to_node_index(vec2 pos) {
    unsigned short retval;
    retval = pos.x;
    retval <<= 8;
    retval |= pos.y;
    return retval;
}

inline unsigned int to_cost_cache_index(vec2 pos1, vec2 pos2) {
    unsigned int retval;
    retval = to_node_index(pos1);
    retval <<= 16;
    retval |= to_node_index(pos2);
    return retval;
}

class GraphEdge;

class GraphNode {
public:
    int network_number = -1; // if multiple disconnected graphs, save performance with this
    vec2 pos;
    std::vector<GraphEdge> warps;
    
    GraphNode(vec2 pos_) {
        pos = pos_;
    }

    GraphNode() {}
};

class GraphEdge {
public:
    int cost;
    GraphNode *destination;

    GraphEdge(GraphNode *destination_, int cost_) {
        cost = cost_;
        destination = destination_;
    }
};

const uint BSIZE = 250;

std::vector<GraphNode> rows[BSIZE];
std::vector<GraphNode> columns[BSIZE];
std::map<unsigned short, GraphNode> nodes;

inline GraphNode get_node(vec2 pos) {
    return nodes[to_node_index(pos)];
}

void connect_nodes(vec2 pos1, vec2 pos2, int cost) {
    GraphNode first = get_node(pos1);
    GraphNode second = get_node(pos2);

    first.warps.push_back(
        GraphEdge(&second, cost)
    );

    second.warps.push_back(
        GraphEdge(&first, cost)
    );
}

class AStarNode {
public:
    unsigned short cost;
    unsigned short heuristic;
    vec2 pos;

    AStarNode(unsigned short cost_, unsigned short heuristic_, vec2 pos_) {
        cost = cost_;
        heuristic = heuristic_;
        pos = pos_;
    }
};

class Compare
{
public:
    bool operator() (AStarNode a, AStarNode b)
    {
        return a.cost + a.heuristic > b.cost + b.heuristic;
    }
};

/* unused
inline vec2 vec2_add(vec2 a, vec2 b) {
    return vec2 { (unsigned char) (a.x + b.x), (unsigned char) (a.y + b.y) };
}*/

inline bool vec2_neq(vec2 a, vec2 b) {
    return (a.x != b.x || a.y != b.y); 
}

inline bool vec2_eq(vec2 a, vec2 b) {
    return (a.x == b.x && a.y == b.y);
}

unsigned char hgt, wid;

// vec4 => unsigned int
std::unordered_map<unsigned int, unsigned int> calculated_solutions;

int heuristic(vec2 pos, vec2 end) {
    if (vec2_eq(pos, end)) { return 0; }
    if (pos.x == end.x || pos.y == end.y) {
        return 1;
    }
    return 5;
}

int algorithm(vec2 start, vec2 end) {
    GraphNode start_node = get_node(start);
    GraphNode end_node = get_node(end);

    if (start_node.network_number != -1 && end_node.network_number != -1 && start_node.network_number != end_node.network_number) {
        return -1;
    }

    unsigned int cache_idx1 = to_cost_cache_index(start, end);
    unsigned int cache_idx2 = to_cost_cache_index(end, start);

    auto iterator = calculated_solutions.find(cache_idx1);
    if (iterator != calculated_solutions.end()) {
        return (*iterator).second;
    }
    calculated_solutions.find(cache_idx2);
    if (iterator != calculated_solutions.end()) {
        return (*iterator).second;
    }

    Queue queue;
    std::unordered_set<unsigned short> already_visited;

    already_visited.insert(to_node_index(start));

    queue.push(AStarNode(0, heuristic(start, end), start));
    //std::cout << "s: " << start.x << ' ' << start.y << ", e: " << end.x << ' ' << end.y << ", heuristic: " << heuristic(start, end) << std::endl;
    while (!queue.empty()) {
        AStarNode cur = queue.top();
        queue.pop();
        //std::cout << "cpos: (" << cur.pos.x << ", " << cur.pos.y << "), cost: " << cur.cost << ", heuristic: " << cur.heuristic << std::endl;
        
        if (start_node.network_number != -1) {
            GraphNode cur_node = get_node(cur.pos);
            cur_node.network_number = start_node.network_number;
        }

        //connect_nodes(start, cur.pos, cur.cost);
        
        if (vec2_eq(cur.pos, end)) {
            calculated_solutions[to_cost_cache_index(cur.pos, end)] = cur.cost;
            return cur.cost;
        }

        for (GraphNode node : columns[cur.pos.x]) {
            //std::cout << "cx: " << x << std::endl;
            vec2 pos = node.pos;
            
            //std::cout << (!board[pos.y][pos.x]) << (cur.pos.x == x) << (already_visited.count(to_node_index(pos)) > 0) << std::endl;
            if (already_visited.count(to_node_index(pos)) > 0) { continue; }

            already_visited.insert(to_node_index(pos));
            queue.push(AStarNode(cur.cost + 1, heuristic(pos, end), pos));
        }

        for (GraphNode node : rows[cur.pos.y]) {
            //std::cout << "cy: " << y << std::endl;
            vec2 pos = node.pos;
            
            //std::cout << (!board[pos.y][pos.x]) << (cur.pos.y == y) << (already_visited.count(to_node_index(pos)) > 0) << std::endl;
            if (already_visited.count(to_node_index(pos)) > 0) { continue; }

            already_visited.insert(to_node_index(pos));
            queue.push(AStarNode(cur.cost + 1, heuristic(pos, end), pos));
        }

        for (GraphEdge edge : nodes[to_node_index(cur.pos)].warps) {
            GraphNode *node = edge.destination;
            vec2 pos = node->pos;

            if (already_visited.count(to_node_index(pos)) > 0) { continue; }

            already_visited.insert(to_node_index(pos));
            queue.push(AStarNode(cur.cost + edge.cost, heuristic(node->pos, end), pos));

        }
    }

    return -1;
}

int main() {
    uint q;

    std::cin >> hgt >> wid >> q;
    // because unsigned char, c++ treats as character input 
    hgt -= '0';
    wid -= '0';
    //std::cout << "hgt: " << (int) hgt << ", wid:" << (int) wid << std::endl;

    char buf[BSIZE+1];
    for (unsigned char y = 0; y < hgt; y++) {
        //std::cout << "y: " << (int)y;
        std::cin >> buf;
        for (unsigned char x = 0; x < wid; x++) {
            //std::cout << "x: " << (int)x;
            if (is_movable(buf[x])) {
                GraphNode node = GraphNode({ x, y });

                columns[x].push_back(node);
                rows[y].push_back(node);
                nodes[to_node_index(node.pos)] = node;
            }
        }
    }

    for (uint i = 0; i < q; i++) {
        //std::cout << "i: " << (int)i;
        unsigned short startx, starty, endx, endy;
        std::cin >> starty >> startx >> endy >> endx;
        
        vec2 start = { (uc) (startx - 1), (uc) (starty - 1) };
        vec2 end = { (uc) (endx - 1), (uc) (endy - 1) };
        
        std::cout << algorithm(start, end) << std::endl;
    }

    return 0;
}

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 3

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 4

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 5

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 6

Group: 2, 5

Verdict: WRONG ANSWER

Test 7

Group: 2, 5

Verdict: WRONG ANSWER

Test 8

Group: 2, 5

Verdict: WRONG ANSWER

Test 9

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 10

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 11

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 12

Group: 4, 5

Verdict: WRONG ANSWER

Test 13

Group: 4, 5

Verdict: WRONG ANSWER

Test 14

Group: 4, 5

Verdict: WRONG ANSWER

Test 15

Group: 5

Verdict: WRONG ANSWER

Test 16

Group: 5

Verdict: WRONG ANSWER

Test 17

Group: 5

Verdict: WRONG ANSWER

Test 18

Group: 5

Verdict: WRONG ANSWER

Test 19

Group: 5

Verdict: WRONG ANSWER

Test 20

Group: 5

Verdict: WRONG ANSWER

Test 21

Group: 5

Verdict: WRONG ANSWER

Test 22

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 23

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 24

Group: 5

Verdict: WRONG ANSWER

Test 25

Group: 5

Verdict: WRONG ANSWER

Test 26

Group: 5

Verdict: WRONG ANSWER

Test 27

Group: 5

Verdict: WRONG ANSWER