Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<algorithm>
- #include<iostream>
- #include<vector>
- #include<queue>
- using namespace std;
- int h, l;
- vector<vector<int>> jumps = {{2,1}, {2,-1}, {-2,1}, {-2,-1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
- bool is_exist_way(int x, int y) {
- return (x >= 0 && y >= 0 && y <= h && x <= l);
- }
- vector<int> d;
- void bfs(int source, int n, vector<vector<int>> &g) {
- d.resize(h * l);
- fill(d.begin(), d.end(), -1);
- queue<int> q;
- q.push(source);
- d[source] = 0;
- while (!q.empty()) {
- int v = q.front();
- q.pop();
- for (int i = 0; i != g[v].size(); ++i) {
- if (d[i] == -1) {
- d[i] = d[v] + 1;
- q.push(i);
- }
- }
- }
- }
- int main() {
- cin >> l >> h;
- int s, t;
- cin >> s >> t;
- int trap = s * l + t;
- int n;
- cin >> n;
- vector<int> fleas(n);
- for (int i = 0; i != n; ++i) {
- int x, y;
- cin >> x >> y;
- fleas[i] = x * l + y;
- }
- vector<vector<int>> g(h * l);
- for (int i = 0; i != l; ++i) {
- for (int j = 0; j != h; ++j) {
- for (int k = 0; k <= 7; ++k) {
- int x = i + jumps[k][0];
- int y = j + jumps[k][1];
- if (is_exist_way(x, y)) {
- g[i*l + j].emplace_back(x*l + y);
- }
- }
- }
- }
- bfs(trap, g.size(), g);
- int sum = -1;
- for (int i = 0; i != n; ++i) {
- sum += d[fleas[i]];
- }
- if (sum == -1) {
- cout << "-1";
- } else {
- cout << sum + 1;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement