Hypyt

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <unordered_map>
 
using namespace std;
 
int minDist(vector<vector<bool>>& grid, vector<vector<bool>>& rowAccess, vector<vector<int>>& rowDists, int n, int x1, int y1, int x2, int y2){
    if (!grid[y2][x2] || rowDists[y1][y2]==-1){
        return -1;
    }
    if (x1==x2 && y1==y2){
        return 0;
    }
    if (x1==x2 || y1==y2){
        return 1;
    }
 
    vector<int> startParities;
 
    int k = rowDists[y1][y2];
    int startParity=0;
    for (int y=0;y<n;y++){
        if (grid[y][x1]){
            if (rowDists[y][y2]==k-1){
                startParity=1;
                startParities.push_back(y);
            }
        }
    }
 
    vector<int> endParities;
 
 
    int endParity=0;
    for (int y=0;y<n;y++){
        if (grid[y][x2]){
            if (rowDists[y][y1]==k-1){
                endParity=1;
                endParities.push_back(y);
            }
        }
    }
    int totalParity=max(startParity, endParity);
    if (endParity==1 && startParity==1){
        for (int startIndex : startParities){
            for (int endIndex : endParities){
                if (rowDists[startIndex][endIndex]==k-2){
                    totalParity=2;
                    return 2*k+1-totalParity;
                }
            }
        }
    }
    //cout<<"k: "<<k<<" startPar: "<<startParity<<" endPar: "<<endParity<<"\n";
    return 2 * k + 1 - totalParity;
}
 
void calcRowDists(vector<vector<bool>>& rowAcces, vector<vector<int>>& rowDists, int n){
    for (int i=0;i<n;i++){
        stack<int> curRows;
        stack<int> nextRows;
        nextRows.push(i);
        vector<bool> doneRows(n,false);
        doneRows[i]=true;
        rowDists[i][i]=0;
        int k=1;
        while (!nextRows.empty()){
            curRows=nextRows;
            nextRows=stack<int>();
            while (!curRows.empty()){
                int curRow=curRows.top();
                for (int row=0;row<n;row++){
                    if (rowAcces[curRow][row] && !doneRows[row]){
                        nextRows.push(row);
                        doneRows[row]=true;
                        rowDists[i][row]=k;
                    }
                }
                curRows.pop();
            }
            k++;
        }
    }
}
 
int main(){
    int n,m,q;
    cin>>n>>m>>q;
 
    vector<vector<bool>> grid(n, vector<bool>(m,0));
    vector<vector<bool>> rowAccess(n, vector<bool>(n, false));
    vector<vector<int>> rowDists(n, vector<int>(n, -1));
 
    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){
                rowAccess[row][row1]=true;
            }
        }
    }
 
    calcRowDists(rowAccess, rowDists, 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, rowAccess, rowDists , n, x1-1, y1-1, x2-1, y2-1)<<"\n";
    }
    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: ACCEPTED

Test 7

Group: 2, 5

Verdict: ACCEPTED

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

Test 12

Group: 4, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 4, 5

Verdict: ACCEPTED

Test 15

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 5

Verdict: ACCEPTED

Test 18

Group: 5

Verdict: ACCEPTED

Test 19

Group: 5

Verdict: ACCEPTED

Test 20

Group: 5

Verdict: ACCEPTED

Test 21

Group: 5

Verdict: ACCEPTED

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

Test 27

Group: 5

Verdict: ACCEPTED