Hypyt

input/code.cpp: In function 'int bidirectional_bfs(int, int, Node, Node)':
input/code.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for(int c=0; c<current_start.connections.size(); c++){
      |                      ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(int c=0; c<current_end.connections.size(); c++){
      |                      ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp:44:13: warning: unused variable 'move_count' [-Wunused-variable]
   44 |         int move_count = q_end.front().second;
      |             ^~~~~~~~~~
input/code.cpp: In function 'std::vector<Node*> merge_without(std::vector<Node*>, std::vector<Node*>, Node)':
input/code.cpp:65:19: warning: co...

#include <bits/stdc++.h>

using namespace std;

struct Node{
    int x;
    int y;
    vector<Node *> connections;
};

int bidirectional_bfs(int n, int m, Node start_node, Node end_node){
    unordered_set<int> visited_start;
    visited_start.insert(start_node.x + start_node.y*m);
    unordered_set<int> visited_end;
    visited_end.insert(end_node.x + end_node.y*m);
    
    queue<pair<Node*, int>> q_start; // {Node, move_count}
    queue<pair<Node*, int>> q_end; // {Node, move_count}
    q_start.push({&start_node, 0});
    q_end.push({&end_node, 0});
    

    while (q_start.size() > 0 && q_end.size() > 0){
        int start_move_count = q_start.front().second;
        int end_move_count = q_end.front().second;
        
        // Search start
        Node current_start = *q_start.front().first;
        q_start.pop();
    
        for(int c=0; c<current_start.connections.size(); c++){
            int v = (*current_start.connections[c]).x + (*current_start.connections[c]).y * m;
            if(visited_start.find(v) == visited_start.end()){
                q_start.push({current_start.connections[c], start_move_count+1});
                visited_start.insert(v);
            }
            if(visited_end.find(v) != visited_end.end()){
                return start_move_count + end_move_count + 1;
            }
        }
        
        // Search end
        Node current_end = *q_end.front().first;
        int move_count = q_end.front().second;
        q_end.pop();
    
        for(int c=0; c<current_end.connections.size(); c++){
            int v = (*current_end.connections[c]).x + (*current_end.connections[c]).y * m;
            if(visited_end.find(v) == visited_end.end()){
                q_end.push({current_end.connections[c], end_move_count+1});
                visited_end.insert(v);
            }
            if(visited_start.find(v) != visited_start.end()){
                return start_move_count + end_move_count;
            }
        }
        
    }
    
    return -1;
}

vector<Node*> merge_without(vector<Node*> list1, vector<Node*> list2, Node exclude){
    vector<Node*> list3;
    for(int i=0; i<list1.size(); i++){
        if(exclude.x != (*list1[i]).x || exclude.y != (*list1[i]).y){
            list3.push_back(list1[i]);
        }
    }
    for(int i=0; i<list2.size(); i++){
        if(exclude.x != (*list2[i]).x || exclude.y != (*list2[i]).y){
            list3.push_back(list2[i]);
        }
    }
    return list3;
}

int main() {
   
    int n, m, q;
    cin >> n >> m >> q;
   
    vector<Node> nodes;
    map<pair<int, int>, Node> node_map;
    
    vector<vector<Node*>> rows;
    vector<vector<Node*>> cols;
    
    for(int i=0; i < n; i++){
        for(int j=0; j < m; j++){
            char val;
            cin >> val;
            if(val == '*') continue;
            Node node = {j, i, {}};
            nodes.push_back(node);
        }
    }
    
    for(int i=0; i < n; i++){ rows.push_back({}); }
    for(int j=0; j < m; j++){ cols.push_back({}); }
    
    for(int k=0; k < nodes.size(); k++){ rows[nodes[k].y].push_back(&nodes[k]); }
    for(int k=0; k < nodes.size(); k++){ cols[nodes[k].x].push_back(&nodes[k]); }

    for(int k=0; k < nodes.size(); k++){
        nodes[k].connections = merge_without(rows[nodes[k].y], cols[nodes[k].x], nodes[k]);
        node_map[{nodes[k].x, nodes[k].y}] = nodes[k];
    }
    
    vector<int> results;
    for(int i=0; i < q; i++){
        int x1, y1, x2, y2;
        cin >> y1 >> x1 >> y2 >> x2;

        Node start_node = node_map[{x1-1, y1-1}];
        Node end_node = node_map[{x2-1, y2-1}];
        
        results.push_back(bidirectional_bfs(n, m, start_node, end_node));
    }
    
    for(int i=0; i<q; i++){
        cout << results[i] << "\n";
    }

    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: 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: WRONG ANSWER