You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
32 lines
1.1 KiB
C++
32 lines
1.1 KiB
C++
#define _CRT_SECURE_NO_WARNINGS
|
|
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
const pair<int, int> dirs[] = {{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
|
|
int main()
|
|
{
|
|
auto pack = [](int64_t hi, int64_t lo) { return hi << 32 | lo; };
|
|
unordered_map<int, unordered_map<int, bool>> m;
|
|
unordered_set<int64_t> s;
|
|
int x0, y0, x1, y1, n, r, a, b;
|
|
scanf("%d%d%d%d%d", &x0, &y0, &x1, &y1, &n);
|
|
while (n--)
|
|
{
|
|
scanf("%d%d%d", &r, &a, &b);
|
|
auto &row = m[r];
|
|
for (int i = a; i <= b; i++) row[i] = true;
|
|
}
|
|
queue<tuple<int, int, int>> q;
|
|
int ans = -1;
|
|
for (q.push({x0, y0, 0}); !q.empty() && ans == -1; q.pop())
|
|
{
|
|
auto [x, y, l] = q.front();
|
|
if (x == x1 && y == y1) ans = l;
|
|
for (auto [dx, dy] : dirs)
|
|
if (m[x + dx][y + dy] && s.count(pack(x + dx, y + dy)) == 0)
|
|
q.push({x + dx, y + dy, l + 1}), s.insert(pack(x + dx, y + dy));
|
|
}
|
|
printf("%d", ans);
|
|
return 0;
|
|
}
|