Hypyt

#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

struct item{
    pair<int, int> pos;
    int dist;
    int start_X;
};
struct pack{
    int dist;
    int startX;
    int endX;
};

vector<pack> evil_BFS(int start_row, const vector<int> rows[], bool visited[],
    int m, const vector<int> columns[], int n){
    //memset(visited, false, n*m);
    queue<item> nodes;
    vector<int> start = rows[start_row];
    vector<pack> distances(n, {-1, -1, -1});
    for(int& pos : start){
        nodes.push({{pos, start_row}, 0, pos});
        visited[start_row * m + pos] = true;
        //cout << "start "<< pos << " "<<start_row << char(10);
    }
    while (!nodes.empty()){
        item next = nodes.front();
        nodes.pop();
        int X = next.pos.first;
        int Y = next.pos.second;

        //cout << "next " << X << " " << Y << " " << next.dist <<char(10);

        if(distances[Y].dist == -1){
            distances[Y].dist = next.dist;
            distances[Y].startX = next.start_X;
            distances[Y].endX = X; 
        }

        for(int a : rows[Y]){
            //cout << "row "<<a << Y<<char(10);
            if(!visited[Y * m + a]){
                visited[Y * m + a] = true;
                nodes.push({{a, Y}, next.dist + 1, next.start_X});
            }
        }
        for(int a : columns[X]){
            if(!visited[a * m + X]){
                visited[a * m + X] = true;
                nodes.push({{X, a}, next.dist + 1, next.start_X});
            }
        }
    }
    /*for(int i = 0; i < n; i++){
        if(distances[i] == 0 && i != start_row){
            //distances[i] = -1;
        }
    }*/
    return distances;
}

int main(){
    // n height, m width
    int n, m, q;
    cin >> n >> m >> q;
    char grid[m][n];
    bool visited[n*m] = {0};
    int ans[q] = {};

    vector<int> rows[n] = {};
    vector<int> columns[m] = {};

    vector<vector<pack>> dist(n);

    for (int i = 0; i < n ; i++){
        string line;
        cin >> line;
        for(int j = 0; j < m ; j++){
            grid[i][j] = line[j];
            if(grid[i][j] == '.'){
                rows[i].emplace_back(j);
                columns[j].emplace_back(i);
            }
        }
    }
    for(int i = 0; i < n; i++){
        memset(visited, 0, m*n);
        dist[i] = evil_BFS(i, rows, visited, m, columns, n);
    }
    for(int i = 0; i < q; i++){
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;

        if(!(y1==y2 && x1 == x2)){
            pack current = dist[y1-1][y2-1];
            if(current.dist == -1){
                ans[i] = -1;
            }else{
                if(current.startX == x1 && current.endX == x2 && current.dist != 0){
                    ans[i] = current.dist;
                }else if(current.startX == current.endX && current.dist == 0){
                    ans[i] = 1;
                }else if(current.startX == x1 && current.endX != x2){
                    ans[i] = current.dist + 1;
                }else if(current.startX != x1 && current.endX == x2){
                    ans[i] = current.dist + 1;
                }else{
                    ans[i] = current.dist + 2;
                }
            }
        }else{
            ans[i] = 0;
        }
    }
    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: 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: 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: 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: TIME LIMIT EXCEEDED

Test 16

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 5

Verdict: TIME LIMIT EXCEEDED

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: RUNTIME ERROR

Test 23

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 24

Group: 5

Verdict: RUNTIME ERROR

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED