Hypyt

#include <algorithm>
#include <climits>
#include <deque>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;

const int INF = 501;

int main() {
  int n, m, q;
  cin >> n >> m >> q;

  vector<string> grid(n);
  for (int i = 0; i < n; ++i) {
    string row;
    cin >> row;
    grid[i] = row;
  }

  int totalNodes = n + m;

  // Build adjacency
  vector<vector<int>> adj(totalNodes);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (grid[i][j] == '.') {
        adj[i].push_back(n + j);
        adj[n + j].push_back(i);
      }
    }
  }

  // BFS for distances
  static int dist[500][500];
  for (int i = 0; i < totalNodes; ++i) {
    for (int j = 0; j < totalNodes; ++j) {
      dist[i][j] = INF;
    }

    deque<int> dq;
    dist[i][i] = 0;
    dq.push_back(i);
    while (!dq.empty()) {
      int u = dq.front();
      dq.pop_front();
      int d = dist[i][u];

      for (int v : adj[u]) {
        if (dist[i][v] == INF) {
          dist[i][v] = d + 1;
          dq.push_back(v);
        }
      }
    }
  }

  while (q--) {
    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    // Convert 1-indexed to 0-indexed
    --r1;
    --c1;
    --r2;
    --c2;

    // monster cells
    if (grid[r1][c1] == '*' || grid[r2][c2] == '*') {
      cout << "-1\n";
      continue;
    }

    // same cell
    if (r1 == r2 && c1 == c2) {
      cout << "0\n";
      continue;
    }

    // same row or column
    if (r1 == r2 || c1 == c2) {
      cout << "1\n";
      continue;
    }

    c1 += n;
    c2 += n;
    int minDist = INF;
    minDist = min(minDist, dist[r1][r2]);
    minDist = min(minDist, dist[r1][c2]);
    minDist = min(minDist, dist[c1][r2]);
    minDist = min(minDist, dist[c1][c2]);
    if (minDist == INF) {
      cout << "-1\n";
    } else {
      cout << minDist + 1 << "\n";
    }
  }

  return 0;
}

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

Test 27

Group: 5

Verdict: ACCEPTED