g.cpp

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <list>
 
#define SIZEOF(a) (sizeof(a)/sizeof(a[0]))
#define FILL(a,b) fill(a,a+SIZEOF(a),b)
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define FORARR(i,a) for(unsigned i=0; i<SIZEOF(a); i++)
#define FOREACH(a,b) for(__typeof((b).begin()) a = (b).begin(); a!=(b).end(); a++)
#define GETI(a) scanf("%d ", &a);
#define SWAP(a,b) { __typeof(a) t = a; a = t; b = t; }
 
using namespace std;
 
struct coords {
    int x,y;
    coords(int x, int y) : x(x),y(y) {}
};
 
 
int main(void)
{
	int R,C;
	cin >> R >> C;
	int startX, startY;
	cin >> startX >> startY;
	int endX, endY;
	cin >> endX >> endY;
 
	while (!feof(stdin)) {
 
	  vector<vector<int> > visited(max(R,C)+1, vector<int>(max(R,C)+1,-1));
	  visited[startX][startY] = 0;
 
	  queue<coords> q;
	  q.push(coords(startX, startY));
 
	  while (!q.empty()) {
		coords c = q.front();
		q.pop();
// 		cerr << "at " << c.x << " " << c.y << endl;
		coords nbs[] = {
		  coords(c.x-1, c.y-2),
		  coords(c.x-1, c.y+2),
		  coords(c.x+1, c.y-2),
		  coords(c.x+1, c.y+2),
		  coords(c.x-2, c.y-1),
		  coords(c.x-2, c.y+1),
		  coords(c.x+2, c.y-1),
		  coords(c.x+2, c.y+1),
		};
		FORARR(i,nbs) {
		    coords nb = nbs[i];
		    // validate...
		    if (nb.x < 1 || nb.x > R || nb.y < 1 || nb.y > C)
		      continue; // bad
		    if (visited[nb.x][nb.y] > 0) continue;
		    visited[nb.x][nb.y] = visited[c.x][c.y] + 1;
		    if (nb.x == endX && nb.y == endY) {
			// victory!
			cout << visited[nb.x][nb.y] << endl;
			goto out;
		    }
		    q.push(nb);
		}
 
 
	  }
 
	  cout << "impossible" << endl;
out: {}	  
	  cin >> R >> C;
	  cin >> startX >> startY;
	  cin >> endX >> endY;
	}
 
 
 
 
    return 0;
}