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 (!grid[y2][x2]){
        //cout<<"NOT POSSIBLE\n";
        return -1;
    }
    if (x1==x2 && y1==y2){
        return 0;
    }
    if (x1==x2 || y1==y2){
        return 1;
    }
    vector<int> curRows(n, -1);
    vector<int> nextRows(n, -1);

    vector<int> doneRows(n, true);

    // syynä varmaan se että eri oksat saapuu samaan aikaan, mutta niillä on eri parity tai spessu case

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

    nextRows[y1]=0;
    doneRows[y1]=false;
    int k=1;
    bool done=false;
    int bestCase=999999999;
    while (true){
        //cout<<"k "<<k<<"\n";
        bool didAnything=false;
        curRows=nextRows;
        nextRows.assign(n, -1);
        for (int curRowIndex=0;curRowIndex<n;curRowIndex++){
        //while (!curRows.empty()){
            //Row curRow = curRows.top();
            int curRowParity = curRows[curRowIndex];
            if (curRowParity!=-1){
                for (int row=0;row<n;row++){
                    if (rowAcces[curRowIndex][row]){
                        if (doneRows[row]==k || doneRows[row]==-1){
                            didAnything=true;
                            doneRows[row]=k;
                            //cout<<"row "<<row<<" parity"<<curRowParity<<"\n";
                            if (row==y2){
                                if (grid[curRowIndex][x2]){
                                    bestCase=min(bestCase, 2*k+curRowParity);
                                    done=true;
                                    //return 2*k+curRow.parity;
                                }
                                else{
                                    bestCase=min(bestCase, 2*k+curRowParity+1);
                                    done=true;
                                    //return 2*k+curRow.parity+1;
                                }
                            }
                            if (nextRows[curRowIndex]!=-1){
                                nextRows[curRowIndex]=min(curRowParity, nextRows[curRowIndex]);
                            }
                            else{
                                nextRows[curRowIndex]=curRowParity;
                            }
                        }
                    }
                }
            }
        }
        if (done){
            return bestCase;
        }
        if (!didAnything){
            break;
        }
        k++;
    }
    //cout<<"COULD NOT FIND PATH\n";
    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: 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: WRONG ANSWER

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: 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: WRONG ANSWER

Test 20

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 5

Verdict: WRONG ANSWER

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