Hypyt

#include <bits/stdc++.h>
using namespace std;
vector<vector<char>> t;
vector<vector<vector<pair<size_t, size_t>>>> p;
size_t n, m, q;
// vector<vector<int>> g;
// vector<vector<int>> z;
// void dfs(size_t i, size_t j, int gi)
// {
//   if(z[i][j] || t[i][j] == '*') return;
//   z[i][j] = 1;
//   g[i][j] = gi;
//   for(auto l : p[i][j]) dfs(l.first, l.second, gi);
// }
int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cin >> n >> m >> q;
  t = vector<vector<char>>(n, vector<char>(m));
  for(size_t i {}; i < n; ++i)
    for(size_t j {}; j < m; ++j)
      cin >> t[i][j];
  p = vector<vector<vector<pair<size_t, size_t>>>>(n, vector<vector<pair<size_t, size_t>>>(m));
  for(size_t i {}; i < n; ++i)
    for(size_t j {}; j < m; ++j)
    {
      if(t[i][j] == '*') continue;
      for(size_t k = j + 1; k < m; ++k)
      {
        if(t[i][k] == '*') continue;
        p[i][j].emplace_back(i, k);
        p[i][k].emplace_back(i, j);
      }
    }
  for(size_t j {}; j < m; ++j)
    for(size_t i {}; i < n; ++i)
    {
      if(t[i][j] == '*') continue;
      for(size_t k = i + 1; k < n; ++k)
      {
        if(t[k][j] == '*') continue;
        p[i][j].emplace_back(k, j);
        p[k][j].emplace_back(i, j);
      }
    }
  // z = vector<vector<int>>(n, vector<int>(m));
  // g = vector<vector<int>>(n, vector<int>(m));
  // int gi {};
  // for(size_t i {}; i < n; ++i)
  //   for(size_t j {}; j < m; ++j)
  //     dfs(i, j, gi++);
  unordered_map<size_t, unordered_map<size_t, vector<tuple<size_t, size_t, size_t>>>> qs;
  for(size_t i {}; i < q; ++i)
  {
    size_t y1, x1, y2, x2;
    cin >> y1 >> x1 >> y2 >> x2;
    --y1;
    --x1;
    --y2;
    --x2;
    if(qs[y1][x1].size())
      qs[y1][x1].push_back(make_tuple(y2, x2, i));
    else
      qs[y2][x2].push_back(make_tuple(y1, x1, i));
  }
  vector<int> s(q, 0);
  for(auto y1 : qs)
    for(auto x1 : y1.second)
    {
      vector<vector<int>> d(n, vector<int>(m, -1));
      d[y1.first][x1.first] = 0;
      queue<tuple<size_t, size_t, int>> w;
      w.push(make_tuple(y1.first, x1.first, 0));
      while(!w.empty())
      {
        for(auto l : p[get<0>(w.front())][get<1>(w.front())])
          if(d[l.first][l.second] == -1)
          {
            d[l.first][l.second] = get<2>(w.front()) + 1;
            w.push(make_tuple(l.first, l.second, get<2>(w.front()) + 1));
          }
        w.pop();
      }
      for(auto t : x1.second) s[get<2>(t)] = d[get<0>(t)][get<1>(t)];
    }
  for(int a : s) cout << a << '\n';
}

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 6

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3, 4, 5

Verdict: ACCEPTED

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5

Verdict: ACCEPTED

Test 12

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 4, 5

Verdict: ACCEPTED

Test 15

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 5

Verdict: ACCEPTED

Test 20

Group: 5

Verdict: ACCEPTED

Test 21

Group: 5

Verdict: ACCEPTED

Test 22

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 23

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 24

Group: 5

Verdict: ACCEPTED

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED