2014
11-30

# Knight’s Problem

You must have heard of the Knight’s Tour problem. In that problem, a knight is placed on an empty chess board and you are to determine whether it can visit each square on the board exactly once.

Let’s consider a variation of the knight’s tour problem. In this problem, a knight is place on an infinite plane and it’s restricted to make certain moves. For example, it may be placed at (0, 0) and can make two kinds of moves: Denote its current place as (x,y), it can only move to (x+1,y+2) or (x+2,y+1). The goal of this problem is to make the knight reach a destination position as quickly as possible (i.e. make as less moves as possible).

The first line contains an integer T ( T < 20) indicating the number of test cases.

Each test case begins with a line containing four integer: fx fy tx ty(-5000<=fx,fy,tx,ty<=5000). The knight is originally placed at (fx, fy) and (tx, ty) is its destination.

The following line contains an integer m(0<m<=10), indicating how many kinds of moves the knight can make.

Each of the following m lines contains two integer mx my(-10<=mx,my<=10; |mx|+|my|>0), which means that if a knight stands at (x,y), it can move to (x+mx,y+my).

The first line contains an integer T ( T < 20) indicating the number of test cases.

Each test case begins with a line containing four integer: fx fy tx ty(-5000<=fx,fy,tx,ty<=5000). The knight is originally placed at (fx, fy) and (tx, ty) is its destination.

The following line contains an integer m(0<m<=10), indicating how many kinds of moves the knight can make.

Each of the following m lines contains two integer mx my(-10<=mx,my<=10; |mx|+|my|>0), which means that if a knight stands at (x,y), it can move to (x+mx,y+my).

2
0 0 6 6
5
1 2
2 1
2 2
1 3
3 1
0 0 5 5
2
1 2
2 1

3
IMPOSSIBLE

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <queue>
#include <set>
#include <utility>
#define MAX(a , b) ((a) > (b) ? (a) : (b))
#define sqr(x) ((x) * (x))
#define mp make_pair
typedef long long ll;
using namespace std;
const int maxn = 12;
const int maxm = 400000;
const int kr = 1;
const int prime = 999997;
struct ddd
{
int x,y;
int step;
};
struct node
{
int x,y;
int next;
}edge[maxm];
queue <ddd> Q;
int sx,sy,tx,ty,a,b,c,d,n,idx;

void init()
{
idx = 0;
return;
}

int hash(int x,int y)
{
return (((x << 15) ^ y) % prime + prime) % prime;
}

{
{
if(edge[i].x == x && edge[i].y == y) return false;
}
edge[idx].x = x;
edge[idx].y = y;
return true;
}

{
d = 0;
scanf("%d %d %d %d",&sx,&sy,&tx,&ty);
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d %d",&vec[i][0],&vec[i][1]);
d = MAX(d , sqr(vec[i][0]) + sqr(vec[i][1]));
}
a = ty - sy;
b = sx - tx;
c = sy * tx - sx * ty;
return;
}

bool IsValid(int x,int y)
{
if(sqr(x - sx) + sqr(y - sy) <= sqr(kr) * d) return true;
if(sqr(x - tx) + sqr(y - ty) <= sqr(kr) * d) return true;
if((tx - sx) * (x - sx) + (ty - sy) * (y - sy) < 0) return false;
if((sx - tx) * (x - tx) + (sy - ty) * (y - ty) < 0) return false;
if(sqr(ll(a) * x + b * y + c) <= ll(d) * (sqr(a) + sqr(b))) return true;
return false;
}

void bfs()
{
while(!Q.empty()) Q.pop();
ddd cur,tmp;
tmp.x = sx;
tmp.y = sy;
tmp.step = 0;
Q.push(tmp);
addedge(hash(sx , sy) , sx , sy);
while(!Q.empty())
{
cur = Q.front();
Q.pop();
if(cur.x == tx && cur.y == ty)
{
printf("%d\n",cur.step);
return;
}
for(int i=0;i<n;i++)
{
int xx = cur.x + vec[i][0];
int yy = cur.y + vec[i][1];
if(IsValid(xx , yy) && addedge(hash(xx , yy) , xx , yy))
{
tmp.x = xx;
tmp.y = yy;
tmp.step = cur.step + 1;
Q.push(tmp);
}
}
}
puts("IMPOSSIBLE");
return;
}

int main()
{
int cas;
scanf("%d",&cas);
while(cas--)
{
init();
bfs();
}
return 0;
}

1. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。