Hypyt

#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

class Node{
    public:
        int x,y;
        vector<pair<int, int>> neighbours;
        bool visited = false;
        Node(int a, int b, vector<pair<int, int>> c, bool d) : 
            x(a), y(b), neighbours(c), visited(d) {}
        bool operator==(const Node &a)const {
            return (a.x == x && a.y == y);
        }
};
struct NodeHash{
    size_t operator()(const pair<int, int>& x)const{
        return (static_cast<std::size_t>(x.first) << 16) + x.second;
    }
};
struct PairEq{
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) const{
        return(a.first == b.first && a.second == b.second);
    }
};

struct item{
    Node* node;
    int dist;
};
int BFS(Node start, Node goal, unordered_map<pair<int, int>, Node, NodeHash, PairEq>& map){
    queue<item> nodes;
    Node& s = map.at({start.x, start.y});
    s.visited = true;
    nodes.push({ &s, 0 });
    while (!nodes.empty()){
        item next = nodes.front();
        nodes.pop();
        if(*next.node == goal){
            return next.dist;
        }
        for(pair<int, int> a : next.node -> neighbours){
            Node& b = map.at({a.first, a.second});
            if(!b.visited){
                b.visited = true;
                nodes.push({ &b, next.dist + 1 });
            }
        }
    }
    return -1;
}

int main(){
    // n height, m width
    int n, m, q;
    cin >> n >> m >> q;
    char grid[m][n];
    vector<Node>graph = {};

    unordered_map<pair<int, int>, Node, NodeHash, PairEq> nodeMap = {};

    for (int i = 0; i < n ; i++){
        string line;
        cin >> line;
        for(int j = 0; j < m ; j++){
            grid[j][i] = line[j];
            if(grid[j][i] == '.'){
                Node node = Node(j, i, {}, false); 
                pair<int, int> coord = {j, i};
                nodeMap.insert({coord, node});
            }
        }
    }
    for (auto& entry : nodeMap) {
        Node& node = entry.second;
        int i = node.y; 
        int j = node.x;
        for(int z = 0; z < m; z++){
            if(grid[z][i] == '.' && z != j){
                //cout << z << " "<< i << char(10);
                node.neighbours.emplace_back(z, i);
            }
        }
        for(int z = 0; z < n; z++){
            if(grid[j][z] == '.' && z != i){
                //cout << j << " "<< z << char(10);
                node.neighbours.emplace_back(j, z);
            }
        }
    }
    //cout <<"start" <<char(10);
    int ans[q] = {};
    for(int i = 0; i < q; i++){
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        //cout << y1 << y2 << x1 << x2 << char(10);

        if(!(y1==y2 && x1 == x2)){
            pair<int, int> first = {x1-1, y1-1};
            pair<int, int> second = {x2-1, y2-1};
            if(nodeMap.find(first) == nodeMap.end() || nodeMap.find(second) == nodeMap.end()){
                cout << "not found";
            }else{
                Node start = nodeMap.at(first);
                //cout << start.neighbours.size() << char(10);
                //cout << start.x << " "<< start.y << char(10);
                Node goal = nodeMap.at(second);
                ans[i] = BFS(start, goal, nodeMap);
                //cout << BFS(start, goal, nodeMap) << char(10);
                }
        }else{
            ans[i] = 0;
        }
        for(auto& cheese : nodeMap){
            Node& node = cheese.second;
            node.visited = false;
        }
    }
    for(int i = 0; i < q; i++){
        cout << ans[i] << char(10);
    }
    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: TIME LIMIT EXCEEDED

Test 7

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

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