Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <algorithm>
- #define pp pair<int, int>
- #define x first
- #define y second
- #define mp make_pair
- using namespace std;
- int main()
- {
- int N, M, p, q, x1, y1, x2, y2;
- cin>>N>>M>>p>>q>>x1>>y1>>x2>>y2;
- bool a[N+1][M+1];
- pp prev[N+1][M+1];
- int d[N+1][M+1];
- queue<pp> qu;
- pp s=mp(x1, y1);
- qu.push (s);
- a[s.x][s.y] = true;
- prev[s.x][s.y].x = -1;
- prev[s.x][s.y].y = -1;
- d[s.x][s.y]=0;
- while (!qu.empty()) {
- pp u = qu.front();
- qu.pop();
- if(u.x+q>0 && u.x+q<=N && u.y+p>0 && u.y+p<=M){
- pp to = mp(u.x+q, u.y+p);
- if(!a[to.x][to.y]){
- a[to.x][to.y]=true;
- qu.push(to);
- d[to.x][to.y]=d[u.x][u.y]+1;
- prev[to.x][to.y].x=u.x;
- prev[to.x][to.y].y=u.y;
- }
- }
- if(u.x+q>0 && u.x+q<=N && u.y-p>0 && u.y-p<=M){
- pp to = mp(u.x+q, u.y-p);
- if(!a[to.x][to.y]){
- a[to.x][to.y]=true;
- qu.push(to);
- d[to.x][to.y]=d[u.x][u.y]+1;
- prev[to.x][to.y].x=u.x;
- prev[to.x][to.y].y=u.y;
- }
- }
- if(u.x-q>0 && u.x-q<=N && u.y+p>0 && u.y+p<=M){
- pp to = mp(u.x-q, u.y+p);
- if(!a[to.x][to.y]){
- a[to.x][to.y]=true;
- qu.push(to);
- d[to.x][to.y]=d[u.x][u.y]+1;
- prev[to.x][to.y].x=u.x;
- prev[to.x][to.y].y=u.y;
- }
- }
- if(u.x-q>0 && u.x-q<=N && u.y-p>0 && u.y-p<=M){
- pp to = mp(u.x-q, u.y-p);
- if(!a[to.x][to.y]){
- a[to.x][to.y]=true;
- qu.push(to);
- d[to.x][to.y]=d[u.x][u.y]+1;
- prev[to.x][to.y].x=u.x;
- prev[to.x][to.y].y=u.y;
- }
- }
- if(u.x+p>0 && u.x+p<=N && u.y+q>0 && u.y+q<=M){
- pp to = mp(u.x+p, u.y+q);
- if(!a[to.x][to.y]){
- a[to.x][to.y]=true;
- qu.push(to);
- d[to.x][to.y]=d[u.x][u.y]+1;
- prev[to.x][to.y].x=u.x;
- prev[to.x][to.y].y=u.y;
- }
- }
- if(u.x-p>0 && u.x-p<=N && u.y+q>0 && u.y+q<=M){
- pp to = mp(u.x-p, u.y+q);
- if(!a[to.x][to.y]){
- a[to.x][to.y]=true;
- qu.push(to);
- d[to.x][to.y]=d[u.x][u.y]+1;
- prev[to.x][to.y].x=u.x;
- prev[to.x][to.y].y=u.y;
- }
- }
- if(u.x+p>0 && u.x+p<=N && u.y-q>0 && u.y-q<=M){
- pp to = mp(u.x+p, u.y-q);
- if(!a[to.x][to.y]){
- a[to.x][to.y]=true;
- qu.push(to);
- d[to.x][to.y]=d[u.x][u.y]+1;
- prev[to.x][to.y].x=u.x;
- prev[to.x][to.y].y=u.y;
- }
- }
- if(u.x-p>0 && u.x-p<=N && u.y-q>0 && u.y-q<=M){
- pp to = mp(u.x-p, u.y-q);
- if(!a[to.x][to.y]){
- a[to.x][to.y]=true;
- qu.push(to);
- d[to.x][to.y]=d[u.x][u.y]+1;
- prev[to.x][to.y].x=u.x;
- prev[to.x][to.y].y=u.y;
- }
- }
- }
- if(!a[x2][y2]){
- cout<<-1<<endl;
- return 0;
- }else{
- int D=d[x2][y2];
- cout<<D<<endl;
- pp f = mp(x2, y2);
- vector<pp> ans;
- ans.push_back(f);
- while(ans.size()<D+1){
- pp last = ans[ans.size()-1];
- pp last_new = mp(prev[last.x][last.y].x, prev[last.x][last.y].y);
- ans.push_back(last_new);
- }
- reverse(ans.begin(), ans.end());
- for(int i=0; i<=D; i++){
- cout<<ans[i].x<<" "<<ans[i].y<<endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement