Hypyt

input/code.cpp: In function 'int main()':
input/code.cpp:199:23: warning: comparison of integer expressions of different signedness: 'int' and 'uint' {aka 'unsigned int'} [-Wsign-compare]
  199 |     for (int y = 0; y < hgt; y++) {
      |                     ~~^~~~~
input/code.cpp:201:27: warning: comparison of integer expressions of different signedness: 'int' and 'uint' {aka 'unsigned int'} [-Wsign-compare]
  201 |         for (int x = 0; x < wid; x++) {
      |                         ~~^~~~~

// 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 <map>
#include <queue>

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


typedef unsigned int uint;

typedef struct vec2 {
    int x;
    int y;
} vec2;

inline long long to_long(vec2 pos) {
    long long retval;
    retval = pos.x;
    retval <<= 32;
    retval |= pos.y;
    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<long long, GraphNode> nodes;

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

void connect_nodes(vec2 pos1, vec2 pos2, int cost) {
    GraphNode first = nodes[to_long(pos1)];
    GraphNode second = nodes[to_long(pos2)];

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

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

class AStarNode {
public:
    int cost;
    int heuristic;
    vec2 pos;

    AStarNode(int cost_, int 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;
    }
};

inline vec2 vec2_add(vec2 a, vec2 b) {
    return vec2 { a.x + b.x, 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);
}

uint hgt, wid;


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 2;
}

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;
    }

    Queue queue;
    std::unordered_set<long long> already_visited;

    already_visited.insert(to_long(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)) {
            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_long(pos)) > 0) << std::endl;
            if (already_visited.count(to_long(pos)) > 0) { continue; }

            already_visited.insert(to_long(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_long(pos)) > 0) << std::endl;
            if (already_visited.count(to_long(pos)) > 0) { continue; }

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

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

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

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

        }
    }

    return -1;
}

int main() {
    uint q;

    std::cin >> hgt >> wid >> q;

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

                columns[x].push_back(node);
                rows[y].push_back(node);
                nodes[to_long({x, y})] = node;
            }
        }
    }

    for (uint i = 0; i < q; i++) {
        int startx, starty, endx, endy;
        std::cin >> starty >> startx >> endy >> endx;
        
        vec2 start = { startx - 1, starty - 1 };
        vec2 end = { endx - 1, 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: 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: 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: TIME LIMIT EXCEEDED

Test 25

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED