Hypyt

#include <iostream>
#include <unordered_map>
#include <string.h> // memset
#include <vector>



typedef unsigned char uchar;



unsigned short height, width;
unsigned long query_count;
int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(NULL);

    std::vector<uchar> rows[250];
    std::vector<uchar> columns[250];

    // what is connected (and not connected) to what?
    // speeds up calculations resulting in -1
    // index with column_index or x
    int networks[250];
    memset(&networks, -1, 250 * sizeof(int));

    int cur_network_num = 0;

    std::cin >> height >> width >> query_count;

    for (unsigned short i = 0; i < height; i++) {
        char buf[251];
        std::cin >> buf;

        for (int j = 0; j < width; j++) {
            if (buf[j] == '.') {
                rows[i].push_back(j);
                columns[j].push_back(i);
                //std::cout << "Connect row idx " << i << " to column idx " << j << std::endl;
            }
        }
    }

    for (unsigned long i = 0; i < query_count; i++) {
        unsigned short start_y, start_x, end_y, end_x;

        std::cin >> start_y >> start_x >> end_y >> end_x;
        start_y--; start_x--; end_y--; end_x--;


        if (start_x == end_x && start_y == end_y) {
            std::cout << "0\n";
            continue;
        }

        if (start_x == end_x || start_y == end_y) {
            std::cout << "1\n";
            continue;
        }

        // if both are -1, neither are set already, we can't do anything with that info
        // if one is not -1, we know they are not in the same network or else the
        // code that set the other to not be -1 would have set them both to not be -1
        if (networks[start_x] != networks[end_x] && (networks[start_x] != -1 || networks[end_x] != -1)) {
            std::cout << "-1\n";
            continue;
        }

        bool available_rows[250];
        bool available_cols[250];

        memset(&available_rows, 0, height);
        memset(&available_cols, 0, width);

        std::vector<uchar> just_added_rows;
        std::vector<uchar> just_added_cols;
        just_added_rows.reserve(height);
        just_added_cols.reserve(width);

        //memset(&just_added_rows, 0, height);
        //memset(&just_added_cols, 0, width);

        just_added_rows.push_back(start_y);
        just_added_cols.push_back(start_x);

        std::vector<uchar> cols_to_add;
        cols_to_add.reserve(width);
        for (int cost = 2;; cost++) {
        
            // set to false when modifying rows_to_add and cols_to_add, if no modifications are made then break out with -1
            bool no_solution = true;

            for (uchar row_idx : just_added_rows) {
                if (available_rows[row_idx]) { continue; }
                
                //std::cout << "Row " << (int) row_idx << std::endl;
                //just_added_rows[row_idx] = false;
                available_rows[row_idx] = true;

                for (uchar col_idx : rows[row_idx]) {
                    if (col_idx == end_x) {
                        std::cout << cost << '\n'; goto complete;
                    }
                    //std::cout << "Add col " << (int) col_idx << std::endl;
                    cols_to_add.push_back(col_idx);
                    no_solution = false;
                }
            }
            just_added_rows.clear();

            for (uchar col_idx : just_added_cols) {
                if (available_cols[col_idx]) { continue; }

                //std::cout << "Col " << (int) col_idx << std::endl;
                //just_added_cols[col_idx] = false;
                available_cols[col_idx] = true;

                for (uchar row_idx : columns[col_idx]) {
                    if (row_idx == end_y) {
                        std::cout << cost << '\n'; goto complete;
                    }
                    //std::cout << "Add row " << (int) row_idx << std::endl;
                    just_added_rows.push_back(row_idx);
                    no_solution = false;
                }
            }
            just_added_cols.clear();

            if (no_solution) {
                std::cout << "-1\n";
                // store network map for use in later calls
                for (uchar i = 0; i < 250; i++) {
                    if (available_cols[i]) {
                        networks[i] = cur_network_num;
                    }
                }
                cur_network_num++;
                goto complete;
            }

            while (cols_to_add.size()) {
                just_added_cols.push_back(cols_to_add.back());
                cols_to_add.pop_back();
            }
        }
complete:
        continue;
    }

    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: TIME LIMIT EXCEEDED

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