Hypyt

#include <bits/stdc++.h>

using namespace std;

// read from file instead of console:
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
typedef bitset<250> ibs;

const int M = 1000000007;
typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef pair<int, int> pi;
typedef queue<int> qi;
typedef stack<int> si;
typedef priority_queue<int> pqi;
typedef deque<int> dqi;
typedef unordered_set<int> seti;
typedef unordered_map<int,int> mapi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef vector<vector<vector<long long>>> vvvll;
typedef pair<long long, long long> pll;
typedef queue<long long> qll;
typedef stack<long long> sll;
typedef priority_queue<long long> pqll;
typedef deque<long long> dqll;
typedef unordered_set<long long> setll;
#define loop(i, a, b) for (int i = a; i < b; i++)
#define rloop(i, a, b) for (int i = a; i > b; i--)
#define each(a, c) for (auto a : c)
#define all(x) x.begin(), x.end()
#define PI M_PI
#define PB push_back
#define P push
#define POB pop_back
#define F first
#define S second
#define sz size()
#define R1(a) int a; cin >> a
#define R2(a, b) int a,b; cin >> a >> b
#define R3(a, b, c) int a,b,c; cin >> a >> b >> c
#define R4(a, b, c, d) int a,b,c,d; cin >> a >> b >> c >> d
#define WS(a) cout << a << " "
#define WN(a) cout << a << "\n"
#define WNL cout << "\n"

// graph of rows
vi g[251];

string mat[251];
int m,n,q;
ibs rows[251];

void construct_graph(){
  loop(i,0,m){
    ibs bs;
    loop(j,0,n){
      if(mat[i][j] == '.') bs.set(j);
    }
    rows[i] = bs;
  }
  loop(i,0,m){
    loop(j,i+1,m){
      auto common = rows[i] & rows[j];
      if (!common.none()) {
        g[i].PB(j);
        g[j].PB(i);
      }
    }
  }
}

// x = col, y = row
int query(int x1, int y1, int x2, int y2){
  if(x1 == x2 && y1 == y2) return 0;
  if(x1 == x2 || y1 == y2) return 1;
  qi bfs;
  qi temp;
  int d[251];
  d[y1] = 6767;
  each(ri, g[y1]){
    if(rows[ri][x1]) { d[ri] = 1; bfs.push(ri); }
    else {d[ri] = 2; temp.push(ri);}
    if(ri == y2) {

      if(!rows[y1][x2]) d[ri]++;
      return d[ri];
    }
  }
  while(!temp.empty()){
    bfs.push(temp.front());
    temp.pop();
  }
  int resd = 67676;
  while(!bfs.empty()){
    int top = bfs.front();
    bfs.pop();
    if(resd <= d[top] + 1) return resd;
    each(ri, g[top]){
      if(d[ri] && ri != y2) continue;
      d[ri] = d[top] + 2;
      if(ri == y2) {
        int tresd = d[ri];
        if(!rows[top][x2]) tresd++;
        resd = min(resd, tresd);
      }
      bfs.push(ri);

    }
  }
  return -1;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> m >> n >> q;
    loop(i,0,m){
      cin >> mat[i];
    }
    construct_graph();
    loop(i,0,q){
      R4(y1,x1,y2,x2);
      cout << query(x1-1,y1-1,x2-1,y2-1) << "\n";
    }
    return 0;
}

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 3

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

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

Test 7

Group: 2, 5

Verdict: WRONG ANSWER

Test 8

Group: 2, 5

Verdict: WRONG ANSWER

Test 9

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 10

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 11

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 12

Group: 4, 5

Verdict: WRONG ANSWER

Test 13

Group: 4, 5

Verdict: WRONG ANSWER

Test 14

Group: 4, 5

Verdict: WRONG ANSWER

Test 15

Group: 5

Verdict: WRONG ANSWER

Test 16

Group: 5

Verdict: WRONG ANSWER

Test 17

Group: 5

Verdict: WRONG ANSWER

Test 18

Group: 5

Verdict: WRONG ANSWER

Test 19

Group: 5

Verdict: WRONG ANSWER

Test 20

Group: 5

Verdict: WRONG ANSWER

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

Test 27

Group: 5

Verdict: ACCEPTED