pku3985 Knight
题目描述
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).
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,my0), which means that if a knight stands at (x,y), it can move to (x+mx,y+my).
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,my0), which means that if a knight stands at (x,y), it can move to (x+mx,y+my).
输出格式
Output one line for each test case. It contains an integer indicating the least number of moves needed for the knight to reach its destination. Output "IMPOSSIBLE" if the knight may never gets to its target position.
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