Hypyt

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

#include <bits/stdc++.h>
using namespace std;
 
void fast_scan(int &number){
    number = 0;
    
    char c = getchar();
    while(c < '0' || '9' < c){
        c = getchar();
    }
 
    for (; (c>='0' && c<='9'); c=getchar()){
        number = number * 10 + c - 48;
    }
}
 
 
int id(pair<char, pair<int, int>> node, int n, int m){
    if(node.first == 'r'){
        return n*m+node.second.second;
    }
    else if(node.first == 'c'){
        return n*m+n+node.second.first;
    }
    else{
        return m*node.second.second+node.second.first;
    }
}
 
vector<int> bfs(int n, int m, vector<vector<pair<char, pair<int, int>>>>& rows, vector<vector<pair<char, pair<int, int>>>>& columns, pair<char, pair<int, int>> start, vector<pair<char, pair<int, int>>>& row_nodes, vector<pair<char, pair<int, int>>>& column_nodes){
    vector<unsigned char> visited (n*m+n+m, 0);
    
    queue<pair<pair<char, pair<int, int>>, int>> q; // {current, move_count}
    q.push({start, 0});
    visited[id(start, n, m)] = 1;
    
    vector<int> table(n+m, -1);
    
    while (q.size() > 0){
        pair<char, pair<int, int>> current = q.front().first;
        int move_count = q.front().second;
        q.pop();
        
 
        if(current.first == 'n'){
            if(!visited[id(row_nodes[current.second.second], n, m)]){
                q.push({row_nodes[current.second.second], move_count});
                visited[id(row_nodes[current.second.second], n, m)] = 1;
            }
 
            if(!visited[id(column_nodes[current.second.first], n, m)]){
                q.push({column_nodes[current.second.first], move_count});
                visited[id(column_nodes[current.second.first], n, m)] = 1;
            }
        }
        else if(current.first == 'r'){
            table[current.second.second] = move_count+1;
            
            for(int c=0; c<rows[current.second.second].size(); c++){
                if(!visited[id(rows[current.second.second][c], n, m)]){
                    q.push({rows[current.second.second][c], move_count+1});
                    visited[id(rows[current.second.second][c], n, m)] = 1;
                }
            }
        }
        else if(current.first == 'c'){
            table[n+current.second.first] = move_count+1;
            for(int c=0; c<columns[current.second.first].size(); c++){
                if(!visited[id(columns[current.second.first][c], n, m)]){
                    q.push({columns[current.second.first][c], move_count+1});
                    visited[id(columns[current.second.first][c], n, m)] = 1;
                }
            }
        }
 
    }
 
    return table;
}
 
int main() {
    char buffer[1<<20];
    setvbuf(stdout, buffer, _IOFBF, sizeof(buffer));
    
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);
   
    vector<vector<char>> grid(n, vector<char>(m, 0));
    
    vector<vector<pair<char, pair<int, int>>>> rows;
    vector<vector<pair<char, pair<int, int>>>> columns;
    vector<pair<char, pair<int, int>>> row_nodes;
    vector<pair<char, pair<int, int>>> column_nodes;
 
    for(int i=0; i < n; i++){
        vector<pair<char, pair<int, int>>> row = {};
        char line[m+1];
        scanf(" %[^\n]", line);
        
        for(int j=0; j < m; j++){
            grid[i][j] = line[j];
            if(grid[i][j] == '*') continue;
            pair<char, pair<int, int>> node = {'n', {j, i}};
            row.push_back(node);
        }
        rows.push_back(row);
 
        pair<char, pair<int, int>> row_node = {'r', {-1, i}};
        row_nodes.push_back(row_node);
    }
 
    for(int j=0; j < m; j++){
        vector<pair<char, pair<int, int>>> column = {};
        for(int i=0; i < n; i++){
            if(grid[i][j] == '*') continue;
            pair<char, pair<int, int>> node = {'n', {j, i}};
            column.push_back(node);
        }
        columns.push_back(column);
 
        pair<char, pair<int, int>> column_node = {'c', {j, 0}};
        column_nodes.push_back(column_node);
    }
    
 
    vector<vector<int>> table(n+m, vector<int>(n+m, -1));
    for(int i=0; i < n; i++){
        pair<char, pair<int, int>> start_row = {'r', {-1, i}};
        table[i] = bfs(n, m, rows, columns, start_row, row_nodes, column_nodes);
    }
    for(int j=0; j < m; j++){
        pair<char, pair<int, int>> start_col = {'c', {j, -1}};
        table[n+j] = bfs(n, m, rows, columns, start_col, row_nodes, column_nodes);
    }
 
    
    
    for(int i=0; i < q; i++){
        int x1, y1, x2, y2;
        fast_scan(y1);
        fast_scan(x1);
        fast_scan(y2);
        fast_scan(x2);
        
        if(y1==y2 && x1==x2){
            printf("%d\n", 0);
            continue;
        }
 
        int p1 = table[y1-1][y2-1];
        int p2 = table[y1-1][n+(x2-1)];
        int p3 = table[n+(x1-1)][y2-1];
        int p4 = table[n+(x1-1)][n+(x2-1)];
        
        printf("%d\n", min(min(p1, p2), min(p3, p4)));
    }
 
    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: ACCEPTED

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