Hypyt

input/code.cpp: In function 'void bfs(std::map<std::__cxx11::basic_string<char>, std::map<std::__cxx11::basic_string<char>, int> >&, std::string, std::vector<std::vector<Node> >&, std::vector<std::vector<Node> >&, Node&)':
input/code.cpp:26:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |             for(int c=0; c<rows[current.pos.second].size(); c++){
      |                          ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp:37:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for(int c=0; c<columns[current.pos.first].size(); c++){
      |                          ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

#include <bits/stdc++.h>
using namespace std;

struct Node {
  char type; // n = cell, r = row, c = column
  pair<int, int> pos;
};

 
void bfs(map<string, map<string, int>>& table, string key, vector<vector<Node>>& rows, vector<vector<Node>>& columns, Node& start){
    set<pair<int, int>> visited;
    
    queue<pair<Node, int>> q; // {current, move_count}
    q.push({start, 0});
    visited.insert({start.pos});
    
    while (q.size() > 0){
        Node current = q.front().first;
        int move_count = q.front().second;
        q.pop();
        

        if(current.type == 'r'){
            table[key]["r"+to_string(current.pos.second)] = move_count;
            
            for(int c=0; c<rows[current.pos.second].size(); c++){
                Node v = rows[current.pos.second][c];
                
                if(visited.find(v.pos) == visited.end()){
                    q.push({v, move_count+1});
                    visited.insert(v.pos);
                }
            }
        }
        else if(current.type == 'c'){
            table[key]["c"+to_string(current.pos.first)] = move_count;
            for(int c=0; c<columns[current.pos.first].size(); c++){
                Node v = columns[current.pos.first][c];
                
                if(visited.find(v.pos) == visited.end()){
                    q.push({v, move_count+1});
                    visited.insert(v.pos);
                }
            }
        }
        else if(current.type == 'n'){
            Node row = {'r', {-1, current.pos.second}};
            if(visited.find(row.pos) == visited.end()){
                q.push({row, move_count});
                visited.insert(row.pos);
            }

            Node column = {'c', {current.pos.first, -1}};
            if(visited.find(column.pos) == visited.end()){
                q.push({column, move_count});
                visited.insert(column.pos);
            }
        }

    }
}
 
int main() {
   
    int n, m, q;
    cin >> n >> m >> q;
   
    vector<vector<char>> grid(n, vector<char>(m, 0));
    
    vector<vector<Node>> rows;
    vector<vector<Node>> columns;
    
    for(int i=0; i < n; i++){
        for(int j=0; j < m; j++){
            cin >> grid[i][j];
        }
    }
    
    for(int i=0; i < n; i++){
        vector<Node> row = {};
        for(int j=0; j < m; j++){
            if(grid[i][j] == '*') continue;
            Node node = {'n', {j, i}};
            row.push_back(node);
        }
        rows.push_back(row);
    }

    for(int j=0; j < m; j++){
        vector<Node> column = {};
        for(int i=0; i < n; i++){
            if(grid[i][j] == '*') continue;
            Node node = {'n', {j, i}};
            column.push_back(node);
        }
        columns.push_back(column);
    }
    
    map<string, map<string, int>> table;
    for(int i=0; i < n; i++){
        Node start_row = {'r', {-1, i}};
        bfs(table, "r" + to_string(i), rows, columns, start_row);
    }
    for(int j=0; j < m; j++){
        Node start_col = {'c', {j, -1}};
        bfs(table, "c" + to_string(j), rows, columns, start_col);
    }

    
    for(int i=0; i < q; i++){
        int x1, y1, x2, y2;
        cin >> y1 >> x1 >> y2 >> x2;
        
        if(y1==y2 && x1==x2){
            cout << 0 << "\n";
            continue;
        }
        string start_row_id = "r" + to_string(y1-1);
        string end_row_id = "r" + to_string(y2-1);
        string start_col_id = "c" + to_string(x1-1);
        string end_col_id = "c" + to_string(x2-1);
        
        if(table[start_row_id].find(end_row_id) == table[start_row_id].end() || table[start_row_id].find(end_col_id) == table[start_row_id].end() || table[start_col_id].find(end_row_id) == table[start_col_id].end() || table[start_col_id].find(end_col_id) == table[start_col_id].end()){
            cout << -1 << "\n";
            continue;
        }

        int row = min(table[start_row_id][end_row_id], table[start_row_id][end_col_id]);
        int col = min(table[start_col_id][end_row_id], table[start_col_id][end_col_id]);

        cout << min(row, col)+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: TIME LIMIT EXCEEDED

Test 7

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3, 4, 5

Verdict: ACCEPTED

Test 12

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 5

Verdict: TIME LIMIT EXCEEDED

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

Test 27

Group: 5

Verdict: ACCEPTED