Hypyt

#include <bits/stdc++.h>
using namespace std;

#define row bitset<250>
#define uin uint8_t

static int h, w, qc;
static std::array<std::bitset<250>, 250> xopt, yopt;
std::unordered_map<uint32_t, int16_t> cache;

inline bool doShare(row &s1, row &s2) {
  row sr = s1 & s2;
  return sr.count();
}

struct ivec2 {
  uin x, y = 0;
  ivec2(int x, int y) : x(x), y(y) {}
  ivec2() {}
  ivec2 operator+(const ivec2 &other) const {
    return ivec2(x + other.x, y + other.y);
  }
  ivec2 operator*(const int &value) const {
    return ivec2(x * value, y * value);
  }
  ivec2 operator/(const int &value) const {
    return ivec2(x / value, y / value);
  }
  friend std::ostream &operator<<(std::ostream &os, const ivec2 &v) {
    return os << "(" << v.x << ", " << v.y << ")";
  }

  bool operator<(const ivec2 &other) const {
    return (x < other.x) || (x == other.x && y < other.y);
  }
  bool operator>(const ivec2 &other) const {
    return (x > other.x) || (x == other.x && y > other.y);
  }
  bool operator<=(const ivec2 &other) const {
    return *this < other || *this == other;
  }
  bool operator>=(const ivec2 &other) const {
    return *this > other || *this == other;
  }
  bool operator==(const ivec2 &other) const {
    return (x == other.x && y == other.y) ? true : false;
  }
};

inline uint16_t getIndex(uint16_t x, uint16_t y) { return y * w + x; }
inline ivec2 getCoords(uint16_t index) { return ivec2(index % w, index / w); }
inline uint32_t packCoords(uin sx, uin sy, uin dx, uin dy) {
  return ((uint32_t)sx << 24) | ((uint32_t)sy << 16) | ((uint32_t)dx << 8) |
         (uint32_t)dy;
}

std::vector<uint16_t> nindices;
std::vector<uint16_t> cindices;

inline int solveslow(uin sx, uin sy, uin dx, uin dy) {
  row vx, vy;
  nindices.clear();
  cindices.clear();
  nindices.push_back(getIndex(dx, dy));
  int step = 1;

  while (!nindices.empty()) {
    std::swap(nindices, cindices);
    for (auto po : cindices) {
      ivec2 p = getCoords(po);
      if (!vy[p.y]) {
        for (int fi = xopt[p.y]._Find_first(); fi < 250;
             fi = xopt[p.y]._Find_next(fi)) {
          if ((yopt[fi] & yopt[sx]).any())
            return step + 3;
          nindices.push_back(getIndex(fi, p.y));
        }
      }
      if (!vx[p.y]) {
        for (int fi = yopt[p.x]._Find_first(); fi < 250;
             fi = yopt[p.x]._Find_next(fi)) {
          if ((xopt[fi] & xopt[sy]).any())
            return step + 3;
          nindices.push_back(getIndex(p.x, fi));
        }
      }
      vx[p.x] = 1;
      vy[p.y] = 1;
    }

    cindices.clear();
    step++;
  }

  return -1;
}

inline int solve(int sx, int sy, int dx, int dy) {
  if (dx == sx && dy == sy)
    return 0;
  else if (dx == sx || dy == sy)
    return 1;

  if (xopt[sy].count() == 1 && yopt[sx].count() == 1)
    return -1;
  if (yopt[dx].count() == 1 && xopt[dy].count() == 1)
    return -1;

  if (yopt[sx][dy])
    return 2;
  if (xopt[sy][dx])
    return 2;

  if ((xopt[sy] & xopt[dy]).any())
    return 3;

  if ((yopt[sx] & yopt[dx]).any())
    return 3;

  uint32_t mcoords = packCoords(sx, sy, dx, dy);
  if (auto sc = cache.find(mcoords); sc != cache.end())
    return sc->second;
  mcoords = packCoords(dx, dy, sx, sy);
  if (auto sc = cache.find(mcoords); sc != cache.end())
    return sc->second;

  int16_t steps = solveslow(sx, sy, dx, dy);
  cache[mcoords] = steps;
  return steps;
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);

  cin >> h >> w >> qc;

  string line;
  getline(cin, line);
  nindices.reserve(500);
  cindices.reserve(500); // prolly not correct size
  for (int y = 0; y < h && std::getline(cin, line); y++) {
    if (line.size() == 0)
      continue;
    for (int x = 0; x < w; x++) {
      if (line[x] == 46) {
        xopt[y][x] = 1;
        yopt[x][y] = 1;
      }
    }
  }
  int sx, sy, dx, dy;
  for (int i = 0; i < qc; i++) {
    cin >> sy >> sx >> dy >> dx;
    sx--;
    sy--;
    dx--;
    dy--;
    std::cout << solve(sx, sy, dx, dy) << "\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: ACCEPTED

Test 7

Group: 2, 5

Verdict: ACCEPTED

Test 8

Group: 2, 5

Verdict: ACCEPTED

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

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 4, 5

Verdict: ACCEPTED

Test 15

Group: 5

Verdict: ACCEPTED

Test 16

Group: 5

Verdict: ACCEPTED

Test 17

Group: 5

Verdict: ACCEPTED

Test 18

Group: 5

Verdict: ACCEPTED

Test 19

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 5

Verdict: WRONG ANSWER

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

Test 27

Group: 5

Verdict: ACCEPTED