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;
    vector<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, {}});
    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.emplace_back(X); 
        }else if(distances[Y].dist == next.dist){
            distances[Y].endX.emplace_back(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, n*m);
        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;

        y1 --;
        x1 --;
        y2 --;
        x2 --;

        if(!(y1==y2 && x1 == x2)){
            pack current = dist[y1][y2];
            if(current.dist == -1){
                ans[i] = -1;
            }else{
                int minimum = 100000;
                if(x1 == x2 || y1 == y2){
                    minimum = 1;
                }
                for(int a : current.endX){
                    //cout << a << char(10);
                    if(current.startX == x1 && a == x2 && current.dist != 0 && current.dist != 1){
                        //cout << "1case 1" << char(10);
                        minimum = min(current.dist, minimum);
                    }else if(current.startX == x2 && a == x1 && current.dist && current.dist == 1){
                        minimum = min(2, minimum);
                        //cout << "faiojfpsj";
                    }
                    else if(current.startX == a && current.dist == 0){
                        //cout << "1case 2" << char(10);
                        minimum = min(1, minimum);
                    }
                    else if(current.startX == x1 && a != x2){
                        //cout << "1case 3" << char(10);
                        minimum = min(current.dist + 1, minimum);
                    }else if(current.startX != x1 && a == x2){
                        //cout << "1case 4" << char(10);
                        minimum = min(current.dist + 1, minimum);
                    }else{
                        //cout << "1case 5" << char(10);
                        minimum = min(current.dist + 2, minimum);
                    }
                }
                pack current = dist[y2][y1];
                for(int a : current.endX){
                    //cout << current.startX << " " << a << char(10);
                    //cout << x2 << " " << x1 << char(10);
                    if(current.startX == x2 && a == x1 && current.dist != 0 && current.dist != 1){
                        //cout << "2case 1" << char(10);
                        minimum = min(current.dist, minimum);
                    }else if(current.startX == x2 && a == x1 && current.dist && current.dist == 1){
                        minimum = min(2, minimum);
                        //cout << "asdoisajd";
                    }
                    else if(current.startX == a && current.dist == 0){
                        //cout << "2case 2" << char(10);
                        minimum = min(1, minimum);
                    }
                    else if(current.startX == x2 && a != x1){
                        //cout << "2case 3" << char(10);
                        minimum = min(current.dist + 1, minimum);
                    }else if(current.startX != x2 && a == x1){
                        //cout << "2case 4" << char(10);
                        minimum = min(current.dist + 1, minimum);
                    }else{
                        //cout << "2case 5" << char(10);
                        minimum = min(current.dist + 2, minimum);
                    }
                }
                ans[i] = minimum;
            }
        }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: 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: ACCEPTED

Test 9

Group: 3, 4, 5

Verdict: ACCEPTED

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 12

Group: 4, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: ACCEPTED

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: ACCEPTED

Test 20

Group: 5

Verdict: WRONG ANSWER

Test 21

Group: 5

Verdict: ACCEPTED

Test 22

Group: 1, 2, 3, 4, 5

Verdict: RUNTIME ERROR

free(): invalid pointer

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