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;
vector<vector<int>>dpalo(1006,vector<int>(1006,0));

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;
}

void bfspalo(int x,int y){
    if(x==-1 or y==-1)return;

    queue<pair<int,int>>q;
    q.push({x,y});
    
    dpalo[x][y]=1;
    int cont=2;

    while(!q.empty()){
        x=q.front().f;
        y=q.front().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 dpalo[nx][ny]==0){
                dpalo[nx][ny]=cont++;
                q.push({nx,ny});
            }
        }
    }
}

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++;
            
            int aux=0;
            if(mat[i][j]=='#'){
                for(int h=0;h<4;h++){
                    int ni=i+mx[h];
                    int nj=j+my[h];
                    if(mat[ni][nj]=='#')aux++;
                }
                if(aux==1){
                    ix=i;
                    iy=j;
                }
            }
        }
    }

    if(c22==0)bfspalo(ix,iy);

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

        // if(c22==0){
        //     cout<<abs(dpalo[x][y]-dpalo[a][b])<<"\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: ACCEPTED

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

Test 11

Subtask: 1, 3, 5

Verdict: ACCEPTED

Test 12

Subtask: 1, 4, 5

Verdict: ACCEPTED

Test 13

Subtask: 1, 3, 4, 5

Verdict: ACCEPTED

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