Surprise Teleport

    1#include <bits/stdc++.h>
    2using namespace std;
    3int main(){
    4    ios::sync_with_stdio(0); cin.tie(0);
    5    //idea is to use bfs to find shortest path without using teleport and then run bfs one more time with teleportion device taken into consideration
    6    int row, col; cin >> row >> col;
    7    int a, b; cin >> a >> b;
    8    int mr, mc; cin >> mr >> mc;
    9    vector<vector<char>> g(row, vector<char>(col));
    10    for(int i = 0; i < row; i++){
    11        for(int j = 0; j < col; j++){
    12            cin >> g[i][j];
    13        }
    14    }
    15    vector<vector<int>> dist(row, vector<int>(col, INT_MAX));
    16    dist[a][b] = 0;
    17    queue<pair<int, int>> q;
    18    vector<pair<int, int>> dir = {{0, 1}, {-1, 0}, {1, 0}, {0, -1}};
    19    q.push({a, b});
    20    while(!q.empty()){
    21        auto[r, c] = q.front(); q.pop();
    22        for(auto[rr, cc] : dir){
    23            int nr = r + rr, nc = c + cc;
    24            if(nr >= 0 && nr < row && nc >= 0 && nc < col && g[nr][nc] != 'X' && dist[nr][nc] == INT_MAX){
    25                dist[nr][nc] = dist[r][c] + 1;
    26                q.push({nr, nc});
    27            }
    28        }
    29    }
    30    int distance = dist[mr][mc];
    31    int t; cin >> t;
    32    vector<pair<int, int>> tel;
    33    for(int i = 0; i < t; i++){
    34        int x, y; cin >> x >> y;
    35        tel.emplace_back(x, y);
    36    }
    37    int tel_dist = INT_MAX;
    38    for(auto[r, c] : tel){
    39        tel_dist = min(tel_dist, dist[r][c]);
    40    }
    41    int ans = distance - (tel_dist != INT_MAX ? tel_dist : distance);
    42    cout << ans << '\n';
    43    return 0;
    44}