Hypyt

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

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(Point a, Point b) {
  return abs(a.x-b.x) + abs(a.y-b.y);
}

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

  bool operator()(const std::pair<Point, int>& a, const std::pair<Point, int>& b) const {
    return heuristic(a.first, target) > heuristic(b.first, 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 = TargetCompare(target);
  auto pq = priority_queue<std::pair<Point, int>, std::vector<std::pair<Point, int>>, TargetCompare>(compare);

  pq.push({start, 0});

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

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

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

    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});
      }
    }

    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);
  }

  //assert(static_cast<int>(grid.size()) == n && static_cast<int>(grid[grid.size() - 1].size()) == m);

  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: WRONG ANSWER

Test 3

Subtask: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 4

Subtask: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 5

Subtask: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 6

Subtask: 2, 5

Verdict: WRONG ANSWER

Test 7

Subtask: 2, 5

Verdict: WRONG ANSWER

Test 8

Subtask: 2, 5

Verdict: WRONG ANSWER

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