Hypyt

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <unordered_map>

using namespace std;

struct Row{
    int parity;
    int index;
};

int minDist(vector<vector<bool>>& grid, vector<vector<bool>>& rowAcces, int n, int x1, int y1, int x2, int y2){
    if (x1==x2 && y1==y2){
        return 0;
    }
    if (x1==x2 || y1==y2){
        return 1;
    }
    stack<Row> curRows={};
    stack<Row> nextRows;

    vector<bool> doneRows(n, true);


    for (int y=0;y<n;y++){
        if (grid[y][x1] && y!=y1){
            doneRows[y]=false;
            nextRows.push({1, y});
            //cout<<"row "<<y<<" parity"<<1<<"\n";
        }
    }

    nextRows.push({0,y1});
    doneRows[y1]=false;
    int k=1;
    while (!nextRows.empty()){
        //cout<<"k "<<k<<"\n";
        curRows=nextRows;
        nextRows={};
        while (!curRows.empty()){
            Row curRow = curRows.top();

            for (int row=0;row<n;row++){
                if (rowAcces[curRow.index][row]){
                    if (doneRows[row]){
                        doneRows[row]=false;
                        //cout<<"row "<<row<<" parity"<<curRow.parity<<"\n";
                        if (row==y2){
                            if (grid[curRow.index][x2]){
                                return 2*k+curRow.parity;
                            }
                            else{
                                return 2*k+curRow.parity+1;
                            }
                        }
                        nextRows.push({curRow.parity, row});
                    }
                }
            }
            curRows.pop();
        }
        k++;
    }
    return -1;
}

int main(){
    int n,m,q;
    cin>>n>>m>>q;

    vector<vector<bool>> grid(n, vector<bool>(m,0));

    vector<vector<bool>> rowAcces(n, vector<bool>(n, false));

    for (int i=0;i<n;i++){
        string s;
        cin>>s;
        for (int j=0;j<m;j++){
            grid[i][j]=(s[j]=='.');
        }
    }

    for (int i=0;i<m;i++){
        vector<int> rows;
        for (int j=0;j<n;j++){
            if (grid[j][i]){
                rows.push_back(j);
            }
        }
        for (int row : rows){
            for (int row1 : rows){
                rowAcces[row][row1]=true;
            }
        }
    }

    //int x1,x2,y1,y2;
    //cin>>y1>>x1>>y2>>x2;
    //cout<<minDist(grid, rowAcces, n, x1-1, y1-1, x2-1, y2-1)<<"\n";


    vector<int> input(4*q, 0);
    for (int i=0;i<q;i++){
        int x1,x2,y1,y2;
        cin>>y1>>x1>>y2>>x2;
        input[4*i+0]=x1;
        input[4*i+1]=y1;
        input[4*i+2]=x2;
        input[4*i+3]=y2;
    }
    
    for (int i=0;i<q;i++){
        int x1=input[4*i+0];
        int y1=input[4*i+1];
        int x2=input[4*i+2];
        int y2=input[4*i+3];
        cout<<minDist(grid, rowAcces, n, x1-1, y1-1, x2-1, y2-1)<<"\n";
    }
}

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

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED