Hypyt

#include <cassert>
#include <fstream>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <cmath>

using namespace std;

struct Point {
  int x;
  int y;

  struct HashFunction {
    size_t operator()(const Point& point) const {
      size_t x_hash = std::hash<int>()(point.x);
      size_t y_hash = std::hash<int>()(point.y);
      return x_hash ^ y_hash;
    }
  };
};

bool operator==(const Point a, const Point b) {
  return (a.x == b.x && a.y == b.y);
}

bool operator!=(const Point a, const Point b) {
  return !(a.x == b.x && a.y == b.y);
}

ostream& operator<<(ostream& out, Point point) {
  out << point.x << "," << point.y;
  return out;
}

int heuristic(const std::pair<Point, int>& a, const Point& target) {
  return a.second+min(abs(a.first.x-target.x), abs(a.first.y-target.y));
}

class Compare {
  const Point target;
  public:
  Compare(Point target) : target { target } {}

  bool operator()(const std::pair<Point, int>& a, const std::pair<Point, int>& b) {
    return heuristic(a, target) > heuristic(b, target);
  }
};

// have to find the same column or row as the target
int find_route(const std::vector<std::string>& grid, const Point& start, const Point& target) {
  const int n = grid.size();
  const int m = grid[0].size();

  auto compare{Compare(target)};
  queue<std::pair<Point, int>> pq;
  pq.push({start, 0});

  std::vector<std::vector<bool>> visited(n, std::vector<bool>(m, false));
  
  visited[start.y][start.x] = true;

  std::set<int> rows;
  std::set<int> cols;

  while (!pq.empty()) {
    auto curr{pq.front()};
    pq.pop();

    if (curr.first == target) return curr.second;

    if (!cols.count(curr.first.y)) {
      cols.insert(curr.first.y);
      for (int col{}; col < m; ++col) {
        Point test{col, curr.first.y};
        if (!visited[test.y][test.x] && grid[test.y][test.x] != '*') {
          visited[test.y][test.x] = true;
          pq.push({test, curr.second+1});
        }
      }
    }
    

    if (!rows.count(curr.first.x)) {
      rows.insert(curr.first.x);
      for (int row{}; row < n; ++row) {
        Point test{curr.first.x, row};
        if (!visited[test.y][test.x] && grid[test.y][test.x] != '*') {
          visited[test.y][test.x] = true;
          pq.push({test, curr.second+1});
        }
      }
    }
  }

  return -1;
}

int main() {
  iostream::ios_base::sync_with_stdio(0);
  cin.tie(0);
  // ifstream in("in.txt");
  //cin.rdbuf(in.rdbuf());

  int n, m, q;
  cin >> n >> m >> q;

  std::vector<std::string> grid;
  for (int i{}; i < n; ++i) {
    std::string line;
    while (line == "") {
      std::getline(std::cin, line);
    }
    grid.push_back(line);
  }

  for (int i{}; i < q; ++i) {
    Point start;
    Point target;

    std::cin >> start.y >> start.x >> target.y >> target.x;
    --start.x;
    --start.y;
    --target.x;
    --target.y;

    int result = find_route(grid, start, target);
    std::cout << result << "\n";
  }

  return 0;
}

Test 1 (public)

Subtask: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Subtask: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 3

Subtask: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 4

Subtask: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 5

Subtask: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 6

Subtask: 2, 5

Verdict: ACCEPTED

Test 7

Subtask: 2, 5

Verdict: ACCEPTED

Test 8

Subtask: 2, 5

Verdict: ACCEPTED

Test 9

Subtask: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 10

Subtask: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 11

Subtask: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 12

Subtask: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 13

Subtask: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 14

Subtask: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 15

Subtask: 5

Verdict: TIME LIMIT EXCEEDED

Test 16

Subtask: 5

Verdict: TIME LIMIT EXCEEDED

Test 17

Subtask: 5

Verdict: TIME LIMIT EXCEEDED

Test 18

Subtask: 5

Verdict: TIME LIMIT EXCEEDED

Test 19

Subtask: 5

Verdict: TIME LIMIT EXCEEDED

Test 20

Subtask: 5

Verdict: TIME LIMIT EXCEEDED

Test 21

Subtask: 5

Verdict: TIME LIMIT EXCEEDED

Test 22

Subtask: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 23

Subtask: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 24

Subtask: 5

Verdict: TIME LIMIT EXCEEDED

Test 25

Subtask: 5

Verdict: TIME LIMIT EXCEEDED

Test 26

Subtask: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Subtask: 5

Verdict: TIME LIMIT EXCEEDED