Hypyt

/*ver 2.0 : virtual row nodes*/
#include <bits/stdc++.h>
using namespace std;

const int N=255;
int n,m,q;

bool grid[N][N];
bool adj[N][N];

struct state{
    int d,first,last;
};

state dp[N][N][N];

const int INF=0x3f3f3f;

void floyd(){
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j){
            dp[0][i][j].last=i;
            dp[0][i][j].first=j;
            if(i==j)dp[0][i][j].d=0;
            else if(adj[i][j]) dp[0][i][j].d=2;
            else dp[0][i][j].d=INF;
        }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                state bef=dp[k-1][i][j];
                state l=dp[k-1][i][k];
                state r=dp[k-1][k][j];
                if(bef.d<=l.d+r.d){
                    dp[k][i][j]=bef;
                }else{
                    dp[k][i][j].last=r.last;
                    dp[k][i][j].first=l.first;
                    dp[k][i][j].d=l.d+r.d;
                }
            }
        }
    }
}

void debug(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            cout<<(dp[n][i][j].d>=0x1f1f1f?-1:dp[n][i][j].d)<<" ";
        cout<<endl;
    }
    cout<<"---"<<endl;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            cout<<dp[n][i][j].first<<" ";
        cout<<endl;
    }
    cout<<"---"<<endl;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            cout<<dp[n][i][j].last<<" ";
        cout<<endl;
    }
}

int search(int x1,int y1,int x2,int y2){
    state route=dp[n][x1][x2];
    int res=route.d;
    int first=route.first;
    int last=route.last;
    if(grid[first][y1]&&grid[x1][y1])--res;
    if(!(grid[last][y2]&&grid[x2][y2]))++res;
    return res;
}
int query(int x1,int y1,int x2,int y2){
    int res=search(x1,y1,x2,y2);
    for(int i=1;i<=n;++i){
        if(i==x2||!grid[i][y2])continue;
        res=min(res,search(x1,y2,i,y2)+1);
    }
    return res;
}

int main(){
    cin>>n>>m>>q;
    char tmpchar;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            {cin>>tmpchar;
            grid[i][j]=(tmpchar=='.'?1:0);}
    for(int i=1;i<=n;++i)//Init the adjacency matrix O(n^3)
        for(int j=1;j<i;++j){
            for(int k=1;k<=m;++k)if(grid[i][k]&&grid[j][k]){
                adj[i][j]=true;
                adj[j][i]=true;
            }
        }
    floyd();
    // debug();
    //Basic Node +1 jump = Row Node (forall).
    for(int i=1;i<=q;++i){//Queries
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        if(x1==x2&&y1==y2){
            cout<<0<<endl;
            continue;
        }
        else if(x1==x2||y1==y2){
            cout<<1<<endl;
            continue;
        }
        else if(grid[x1][y2]||grid[x2][y1]){
            cout<<2<<endl;
            continue;
        }
        else{
            int res=query(x1,y1,x2,y2);
            cout<<(res>=INF?-1:res)<<endl;
        }
    }
    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: WRONG ANSWER

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

Test 16

Group: 5

Verdict: ACCEPTED

Test 17

Group: 5

Verdict: ACCEPTED

Test 18

Group: 5

Verdict: WRONG ANSWER

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