Island

input/code.cpp: In function 'int main()':
input/code.cpp:81:9: error: redeclaration of 'int64_t cnt'
   81 |     int cnt = 0;
      |         ^~~
input/code.cpp:49:9: note: 'int64_t cnt' previously declared here
   49 |     int cnt = 0;
      |         ^~~
input/code.cpp:121:34: warning: unused variable 'mid' [-Wunused-variable]
  121 |         int lo = ja, hi = n - 1, mid = (lo + hi) / 2;
      |                                  ^~~

#include <bits/stdc++.h>

using namespace std;
#define int int64_t
#define all(a) a.begin(), a.end()
#define pb push_back

const int MAXN = 1005;
const int INF = 1e14;

int ind[MAXN][MAXN];
int n,q;
bool left_wall = false;
vector<string> a;
vector<vector<int>> adj;
int dj[4] = {1, 0, -1, 0};
int di[4] = {0, 1, 0, -1};
int pref[MAXN][MAXN];
vector<int> rect = {-1, INF}; // pos i, end j
bool in(int i, int j)
{
    if (i >= 0 && i < n && j >= 0 && j < n)
    {
        return true;
    }
    return false;
}
int range(int ha, int hb, int j)
{
    if (ha > hb)
    {
        swap(ha, hb);
    }
    if (ha == 0)
    {
        return pref[hb][j];
    }
    return pref[hb][j] - pref[ha - 1][j];
}
signed main()
{
    cin >> n >> q;
    a.resize(n);
    adj.resize(n * n);
    for (int i = 0;i < n;i++)
    {
        cin >> a[i];
    }
    int cnt = 0;
    for (int i = 0;i < n;i++)
    {
        for (int j = 0;j < n;j++)
        {
            ind[i][j] = cnt++;
        }
    }
    for (int i = 0;i < n;i++)
    {
        for (int j = 0; j < n;j++)
        {
            if (a[i][j] == '.')
            {
                continue;
            }
            for (int mi = 0;mi < 4;mi++)
            {
                for (int mj = 0;mj < 4;mj++)
                {
                    int ni = i + di[mi];
                    int nj = j + dj[mj];
                    if (in(ni, nj) && a[ni][nj] == '#')
                    {
                        adj[ind[i][j]].pb(ind[ni][nj]);
                        adj[ind[ni][nj]].pb(ind[i][j]);
                    }
                }
            }
        }
    }
    
    int cnt = 0;
    for (int i = 0;i < n;i++)
    {
        for (int j = 0;j < n;j++)
        {
            if (a[i][j] == '.')
            {
                cnt++;
            }
        }
    }
    if (cnt == n * n)
    {
        assert(false);
    }
    for (int j = 0;j < n;j++)
    {
        pref[0][j] = 1;
    }
    for (int i = 1;i < n;i++)
    {
        for (int j = 0;j < n;j++)
        {
            if (a[i][j] == '.')
            {
                pref[i][j] = pref[i - 1][j] + 1;
            }
            else
            {
                pref[i][j] = pref[i - 1][j];
            }
        }
    }
    //cout << "i, j " << rect[0] << " " << rect[1] << '\n'; 
    while (q--)
    {
        int ia,ja, ib, jb;
        cin >> ia >> ja >> ib >> jb;
        ia--,ja--,ib--,jb--;

        int lo = ja, hi = n - 1, mid = (lo + hi) / 2;
        int res = INF;
        // while (lo < hi)
        // {
        //     mid = (lo + hi) / 2;
        //     if (range(ia, ib, mid) == 0)
        //     {
        //         hi = mid;
        //     }
        //     else
        //     {
        //         lo = mid + 1;
        //     }
        // }
        // if (range(ia, ib, lo) == 0)
        // {
        //     res = min(res, abs(ja - lo) + abs(jb - lo));
        // }

        // lo = 0, hi = ja, mid = (lo + hi + 1) / 2;
        // while (lo < hi)
        // {
        //     mid = (lo + hi + 1) / 2;
        //     if (range(ia, ib, mid) == 0)
        //     {
        //         lo = mid;
        //     }
        //     else
        //     {
        //         hi = mid - 1;
        //     }
        // }
        // if (range(ia, ib, lo) == 0)
        // {
        //     res = min(res, abs(ja - lo) + abs(jb - lo));
        // }
        // res += abs(ia - ib);
        for (int j = 0;j < n;j++)
        {
            if (range(ia, ib, j) == 0)
            {
                res = min(res, abs(ia - ib) + abs(ja - j) + abs(jb - j));
            }
            else
            {
                //assert(false);
            }
        }
        //assert(res <= abs(ia - ib) + abs(ja - jb));
        cout << res << '\n';
    }
    return 0;
}


/*
5 3
.....
##...
##...
#....
.....
1 1 5 1
1 2 5 1
1 2 4 2

*/

/*

5 3
.....
....#
..###
....#
.....
1 5 5 5
2 4 4 4
2 1 3 1

*/