Graph problem for BFS

cf_149_c.cpp

// https://codeforces.com/contest/242/problem/C
// You are given lines where king can move (row and column start/finish
// You need to find min number of moves. The grid is too large to use standard bfs 10^9*10^9
// Important - add to visited when add to queue!!! (line 60)
#include <bits/stdc++.h>
using namespace std;

struct hasher {
    size_t operator() (const pair<int,int>& p) const {
        return (((size_t)p.first)<<31)^(p.second);
    }
};

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    int rs, cs, rf, cf;
    cin >> rs >> cs >> rf >> cf;

    int N;
    cin >> N;
    unordered_set< pair<int,int>, hasher > notEmptyCells;
    for (int i = 0; i < N; ++i) {
        int r,c1,c2;
        cin >> r >> c1 >> c2;
        for (int c = c1; c <= c2; ++c) {
            notEmptyCells.emplace(r,c);
        }
    }

    auto neighbours = [] (int x, int y) -> auto {
        vector<pair<int, int>> res;
        res.reserve(8);
        for (int i = -1; i <= 1; ++i) {
            for (int j = -1; j <= 1; ++j) {
                if (i == 0 && j == 0) continue;
                if (x+i >= 0 && x+i <1e9 && y +j >=0 && y+j < 1e9)
                    res.emplace_back(x+i, y+j);
            }
        }
        return res;
    };

    // bfs
    int res = 1e9;
    queue< tuple<int,int, int> > q; // r, c, dist
    unordered_set< pair<int,int>, hasher > visited;
    q.emplace(rs, cs, 0);
    while (!q.empty()) {
        auto[cur_r, cur_c, cur_dist] = q.front();
        q.pop();
        if (cur_r == rf && cur_c == cf) {
            res = cur_dist;
            break;
        }

        for (auto[next_r, next_c] : neighbours(cur_r,cur_c)) {
            if (notEmptyCells.count({next_r, next_c}) &&
                    !visited.count({next_r,next_c})) {
                q.emplace(next_r, next_c, cur_dist + 1);
                visited.emplace(next_r, next_c);
            }
        }
    }
    cout << (res == 1e9? -1 : res) << endl;
    return 0;
}