(p-q)horse.cpp

using namespace std;
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
// #include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>

#define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
#define For(i, a, b) for (int i=(a); i<(b); ++i)
#define D(x) cerr << #x " is " << x << endl

struct point{
	int x, y;
	point (int x, int y) : x(x), y(y){}
	point(){}
};

int v [105][105];      // Visited array
point prev [105][105]; // Previous array

int main() {
	#ifndef LOCAL
	freopen("horse.in", "r", stdin);
	freopen("horse.out", "w", stdout);
	#endif
	
	int n, m, p, r, x1, y1, x2, y2;
	while (cin >> n >> m >> p >> r >> x1 >> y1 >> x2 >> y2){
		
		// Refresh arrays
		for (int i = 0; i <= m; i++){
			for (int j = 0; j <= n; j++){
				v[i][j] = 0;
				prev[i][j] = point(0,0);
			}
		}
		
		// Array of the possible moves
		int dx []= {+p, +r, +p, +r, -p, -r, -p, -r};
		int dy []= {+r, +p, -r, -p, +r, +p, -r, -p};
		
		// Start dfs
		queue < point > q;
		v[x1][y1] = 1;
		prev[x1][y1] = point(-1, -1);
		q.push(point(x1, y1));
		
		while (q.size() > 0){
			point curr = q.front();
			if (curr.x == x2 and curr.y == y2){
				break;
			}
			q.pop();
			for (int i = 0; i < 8; i++){
				int next_x = curr.x + dx[i];
				int next_y = curr.y + dy[i];
				if (next_x > 0 and next_x <= m and next_y > 0 and next_y <= n){
					if (!v[next_x][next_y]){
						v[next_x][next_y] = v[curr.x][curr.y] + 1;
						prev[next_x][next_y] = curr;
						q.push(point(next_x, next_y));
					}
				}
			}
		}
		
		// The position could not be reached
		if (!v[x2][y2]){
			cout << -1 << endl;
		}else{
			int moves = v[x2][y2] - 1;
			
			stack <point> ans;
			point curr = point(x2, y2);
			while (curr.x != -1 or curr.y != -1){
				ans.push(curr);
				curr = prev[curr.x][curr.y];
			}
			assert(ans.size() == moves + 1);
			cout << moves << endl;
			while (ans.size() > 0){
				curr = ans.top();
				ans.pop();
				printf("%d %d\n", curr.x, curr.y);
			}
		}
	}
	
   return 0;
}