首先，题目里给出了一个很关键的信息——陆地之间连通，海洋之间连通。这意味着什么？我们画一张图：

陆地形成的连通块很像一颗树！

但是终究还只是很像，很多点挤在一起，不方便我们建树。

所以为了建树，我们自然而然的想到：把一些点缩成一个点。

具体怎么缩？我们将距离分为两部分：横着移动的距离和竖着移动的距离。而对于每种距离来说，另一个方向的移动没有意义。所以我们分别缩两次，一次将连续的、横坐标相同的点缩成一个点，另一次将连续的、纵坐标相同的点缩成一个点。然后对于两张缩完点后的图，它们都是树，于是直接通过求最近公共祖先求出距离。

例如上面的图缩完之后就是：

和：

上面两张图分别可以求出纵坐标行走的距离和横坐标行走的距离。

最后两个坐标之间的距离就是它们在两张新图上的距离之和。

下附代码：

#include<iostream>
#include<cstdio>
#include<vector>
#define int long long
using namespace std;
int n,q,bl[1005][1005][2],f[2000005][25],tot,rt1,rt2,dep[2000005];
char c[1005][1005];
vector<int>s[2000005];
void dfs(int x,int fa){
    f[x][0]=fa;dep[x]=dep[fa]+1;
    for(int i=0;i<s[x].size();i++){
        int y=s[x][i];
        if(y==fa) continue;
        dfs(y,x);
    }
}
int getlca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
int getdis(int x,int y){
    int k=getlca(x,y);
    return dep[x]+dep[y]-2*dep[k];
}
signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>c[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(c[i][j]=='.') continue;
            if(c[i][j-1]!='#') bl[i][j][0]=++tot,rt1=(!rt1?tot:rt1);
            else bl[i][j][0]=bl[i][j-1][0];
            if(bl[i-1][j][0]&&(bl[i-1][j][0]!=bl[i-1][j-1][0]||bl[i][j-1][0]==0)){
                s[bl[i][j][0]].push_back(bl[i-1][j][0]);
                s[bl[i-1][j][0]].push_back(bl[i][j][0]);
            }
        }
    }
    for(int j=1;j<=n;j++){
        for(int i=1;i<=n;i++){
            if(c[i][j]=='.') continue;
            if(c[i-1][j]!='#') bl[i][j][1]=++tot,rt2=(!rt2?tot:rt2);
            else bl[i][j][1]=bl[i-1][j][1];
            if(bl[i][j-1][1]&&(bl[i][j-1][1]!=bl[i-1][j-1][1]||bl[i-1][j][1]==0)){
                s[bl[i][j][1]].push_back(bl[i][j-1][1]);
                s[bl[i][j-1][1]].push_back(bl[i][j][1]);
            }
        }
    }
    dfs(rt1,0);dfs(rt2,0);
    for(int i=1;i<=20;i++){
        for(int j=1;j<=tot;j++){
            f[j][i]=f[f[j][i-1]][i-1];
        }
    }
    while(q--){
        int x_1,y_1,x_2,y_2;cin>>x_1>>y_1>>x_2>>y_2;
        cout<<getdis(bl[x_1][y_1][0],bl[x_2][y_2][0])+getdis(bl[x_1][y_1][1],bl[x_2][y_2][1])<<endl;
    }
    return 0;
}