Island

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#if defined(__has_include)&&__has_include("custom_h/debugging.h")
#define local_run 1
#include "custom_h\debugging.h"
#else 
#define local_run 0
#endif
// #pragma GCC target ("avx2");
// #pragma GCC optimize ("Ofast");
#define rall(v) v.rbegin(),v.rend()
#define all(v) v.begin(),v.end()
#define keyval find_by_order
#define valkey order_of_key
#define int long long
#define pb push_back
#define s second
#define f first

using namespace __gnu_pbds; 
using namespace std;
template<typename T>
using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<typename T>
using omset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
    
void set_io(string name=""){
    ios_base::sync_with_stdio(0);cin.tie(0);
    if(name.size() and !local_run){
        // freopen((name+".in").c_str(),"r",stdin);
        // freopen((name+".out").c_str(),"w",stdout);
    }
}

const int mx[]={1,-1,0,0,1,-1,-1,1};
const int my[]={0,0,1,-1,1,1,-1,-1};
const int md=1e9+7;
const int oo=1e18;

vector<string>mat;

int bfs(int x,int y,int a,int b){
    vector<vector<int>>dist(1006,vector<int>(1006,oo));
    queue<pair<int,int>>q;
    q.push({x,y});
    
    dist[x][y]=0;
    
    while(!q.empty()){
        x=q.front().f;
        y=q.front().s;
        q.pop();
        
        // cerr<<x<<" "<<y<<"\n";
        
        for(int i=0;i<4;i++){
            int nx=x+mx[i];
            int ny=y+my[i];
            
            if(mat[nx][ny]=='#' and dist[nx][ny]==oo){
                dist[nx][ny]=dist[x][y]+1;
                if(nx==a and ny==b)return dist[nx][ny];
                q.push({nx,ny});
            }
        }
    }
    return 0;
}

vector<int>graph[1000001];
vector<int>dist(1000001,oo);
int bl[1000001][32];
int ind[1001][1001];
int cnd;

void bfspalo(int x,int y){
    if(x==-1 or y==-1)return;
    
    queue<pair<int,pair<int,int>>>q;

    q.push({1,{x,y}});
    ind[x][y]=1;
    
    int cont=2;

    while(!q.empty()){
        int nd=q.front().f;
        x=q.front().s.f;
        y=q.front().s.s;
        
        q.pop();

        for(int i=0;i<4;i++){
            int nx=x+mx[i];
            int ny=y+my[i];

            if(mat[nx][ny]=='#' and ind[nx][ny]==0){
                
                dist[cont]=dist[nd]+1;
                ind[nx][ny]=cont;
                graph[nd].pb(cont);
                bl[cont][0]=nd;
                cnd=cont;

                q.push({cont,{nx,ny}});
                cont++;
            }
        }
    }

    // for(int i=1;i<32;i++){
    //     for(int j=1;j<=cnd;j++){
    //         bl[j][i]=bl[bl[j][i-1]][i-1];
    //         cerr<<bl[j][i]<<" ";
    //     }cerr<<"\n";
    // }
}

int lca(int a,int b){
    if(dist[a]<dist[b])swap(a,b);

    for(int i=31;i>=0;i--){
        if(dist[bl[a][i]]>=dist[b])a=bl[a][i];
    }

    if(a!=b){
        for(int i=31;i>=0;i--){
            if(bl[a][i]!=bl[b][i]){
                a=bl[a][i];
                b=bl[b][i];
            }
        }
        a=bl[a][0];
    }

    return a;
}

void solve(){
    int n,q;
    cin>>n>>q;

    mat.resize(n);

    for(int i=0;i<n;i++){
        cin>>mat[i];
    }

    int ix=-1,iy=-1,c22=0; 

    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-1;j++){
            int c=0;
            
            c+=mat[i][j]=='#';
            c+=mat[i+1][j]=='#';
            c+=mat[i][j+1]=='#';
            c+=mat[i+1][j+1]=='#';
            
            if(c==4)c22++;
            
            if(mat[i][j]=='#'){
                ix=i;
                iy=j;
            }
        }
    }

    if(c22==0){
        // cerr<<ix<<" "<<iy<<"\n";
        bfspalo(ix,iy);
    }

    while(q--){
        int x,y,a,b;
        cin>>x>>y>>a>>b;
        x--;y--;a--;b--;

        if(c22==0){
            x=ind[x][y];
            y=ind[a][b];
            cout<<(dist[x]-dist[lca(x,y)])+(dist[y]-dist[lca(x,y)])<<"\n";
            continue;
        }
        
        if(n<=200 and q<=200){
            cout<<bfs(x,y,a,b)<<"\n";
            continue;
        }

        cout<<abs(x-a)+abs(y-b)<<"\n";
    }
}

int32_t main(){set_io("");
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
}

Test 1

Subtask: 1, 5

Verdict: ACCEPTED

Test 2

Subtask: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 3

Subtask: 1, 5

Verdict: ACCEPTED

Test 4

Subtask: 1, 5

Verdict: ACCEPTED

Test 5

Subtask: 1, 3, 5

Verdict: WRONG ANSWER

Test 6

Subtask: 1, 2, 4, 5

Verdict: ACCEPTED

Test 7

Subtask: 1, 2, 4, 5

Verdict: ACCEPTED

Test 8

Subtask: 1, 5

Verdict: ACCEPTED

Test 9

Subtask: 1, 5

Verdict: ACCEPTED

Test 10

Subtask: 1, 3, 4, 5

Verdict: WRONG ANSWER

Test 11

Subtask: 1, 3, 5

Verdict: WRONG ANSWER

Test 12

Subtask: 1, 4, 5

Verdict: ACCEPTED

Test 13

Subtask: 1, 3, 4, 5

Verdict: WRONG ANSWER

Test 14

Subtask: 1, 4, 5

Verdict: ACCEPTED

Test 15

Subtask: 1, 5

Verdict: ACCEPTED

Test 16

Subtask: 1, 5

Verdict: ACCEPTED

Test 17

Subtask: 1, 5

Verdict: ACCEPTED

Test 18

Subtask: 1, 5

Verdict: ACCEPTED

Test 19

Subtask: 2, 4, 5

Verdict: ACCEPTED

Test 20

Subtask: 2, 4, 5

Verdict: ACCEPTED

Test 21

Subtask: 2, 4, 5

Verdict: ACCEPTED

Test 22

Subtask: 2, 4, 5

Verdict: ACCEPTED

Test 23

Subtask: 3, 5

Verdict: WRONG ANSWER

Test 24

Subtask: 3, 5

Verdict: WRONG ANSWER

Test 25

Subtask: 3, 5

Verdict: WRONG ANSWER

Test 26

Subtask: 3, 5

Verdict: WRONG ANSWER

Test 27

Subtask: 3, 4, 5

Verdict: WRONG ANSWER

Test 28

Subtask: 3, 4, 5

Verdict: WRONG ANSWER

Test 29

Subtask: 4, 5

Verdict: WRONG ANSWER

Test 30

Subtask: 4, 5

Verdict: WRONG ANSWER

Test 31

Subtask: 4, 5

Verdict: WRONG ANSWER

Test 32

Subtask: 4, 5

Verdict: WRONG ANSWER

Test 33

Subtask: 4, 5

Verdict: WRONG ANSWER

Test 34

Subtask: 4, 5

Verdict: WRONG ANSWER

Test 35

Subtask: 5

Verdict: WRONG ANSWER

Test 36

Subtask: 5

Verdict: WRONG ANSWER

Test 37

Subtask: 5

Verdict: WRONG ANSWER

Test 38

Subtask: 5

Verdict: WRONG ANSWER

Test 39

Subtask: 5

Verdict: WRONG ANSWER

Test 40

Subtask: 5

Verdict: WRONG ANSWER

Test 41

Subtask: 5

Verdict: WRONG ANSWER

Test 42

Subtask: 5

Verdict: WRONG ANSWER

Test 43

Subtask: 5

Verdict: WRONG ANSWER

Test 44

Subtask: 5

Verdict: WRONG ANSWER