DH2020_COVID19

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#define task "COVID19"
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e6 + 3;
const int Inf = 1e9 + 7;
int abcdxyzt[N * 3], d[N * 3];
bool ck[N * 3];
int m, n, q;
pair<int, int> rev[N];
int x[] = {1, 0, -1, 0}, y[] = {0, 1, 0, -1};
vector<int> s[N];

#define a(x, y) abcdxyzt[((x)-1) * n + (y)]
#define pos(x, y) (((x)-1) * n + (y))

void Read()
{
    cin >> m >> n >> q;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
        {
            cin >> a(i, j);
            s[i * j].push_back(pos(i, j));
            rev[pos(i, j)] = {i, j};
        }
}

int BFS(int xx, int yy, int z, int t)
{
    memset(ck, 0, sizeof ck);

    queue<int> q;
    d[pos(xx, yy)] = 0;
    q.emplace(pos(xx, yy));
    ck[pos(xx, yy)] = 1;

    while (q.size())
    {
        int c = q.front();
        q.pop();

        if (c == pos(z, t))
            return d[c];

        if (c <= m * n)
        {
            for (int i = 0; i < 4; ++i)
            {
                int u = rev[c].first + x[i],
                    v = rev[c].second + y[i];

                if (u && u <= m && v && v <= n && !ck[pos(u, v)])
                {
                    ck[pos(u, v)] = 1;
                    d[pos(u, v)] = d[c] + 1;
                    q.emplace(pos(u, v));
                }
            }

            if (abcdxyzt[c] <= m * n && !ck[abcdxyzt[c] + m * n])
            {
                ck[abcdxyzt[c] + m * n] = 1;
                d[abcdxyzt[c] + m * n] = d[c] + 1;
                q.emplace(abcdxyzt[c] + m * n);
            }
        }
        else if (c <= m * n * 2)
        {
            if (!ck[c + m * n])
            {
                ck[c + m * n] = 1;
                d[c + m * n] = d[c] + 1;
                q.emplace(c + m * n);
            }
        }
        else
        {
            for (auto i : s[c - m * n * 2])
                if (!ck[i])
                {
                    ck[i] = 1;
                    d[i] = d[c] + 1;
                    q.emplace(i);
                }
        }
    }
    return d[pos(z, t)];
}

void Solve()
{
    int x, y, z, t;
    cin >> x >> y >> z >> t;
    cout << BFS(x, y, z, t) << "\n";
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
        freopen(task ".INP", "r", stdin),
            freopen(task ".OUT", "w", stdout);
    Read();
    while (q--)
        Solve();
}