Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <queue>
- #include <algorithm>
- using namespace std;
- using ss = short;
- const int N = 1000;
- int n, x[N], y[N];
- std::map<std::pair<int, int>, ss> vv;
- bool u[N][N];
- pair<ss, ss> p[N][N];
- int dx[9] = { -1, -1, -1, 0, 0, 0, 1, 1, 1 };
- int dy[9] = { -1, 0, 1, -1, 0, 1, -1, 0, 1 };
- void aiok(std::queue<pair<ss, ss>>& q, ss i, ss v, int x, int y) {
- if(vv.count({x, y})) {
- ss z = vv[{x, y}];
- if(!u[v][z]) p[v][z] = {i, v}, u[v][z] = 1, q.push({v, z});
- }
- }
- int main() {
- std::cin >> n;
- for(int i = 0; i < n; ++i) std::cin >> x[i] >> y[i];
- for(int i = 0; i < n; ++i) vv[{x[i], y[i]}] = i;
- std::queue<pair<ss, ss>> q; q.push({(ss)0, (ss)0}); u[0][0] = 1;
- while(!q.empty()) {
- auto v = q.front(); q.pop();
- const int pv = v.first, cv = v.second;
- const int mx = 2*x[cv]-x[pv], my = 2*y[cv]-y[pv];
- //std::cout << pv << "; " << cv << endl;
- if(cv == n-1) {
- vector<int> res;
- for(int i=pv, j=cv; ; ) {
- int a = i, b = j;
- res.push_back(j);
- if(i == 0) break;
- i = p[a][b].first;
- j = p[a][b].second;
- }
- reverse(res.begin(), res.end());
- std::cout << res.size() << std::endl << "1 ";
- for(int v : res) cout << v+1 << ' ';
- return 0;
- }
- for(int i = 0; i < 9; ++i) {
- const int ax=mx+dx[i], ay=my+dy[i];
- aiok(q, pv, cv, ax, ay);
- }
- }
- std::cout << -1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement