Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Knight's Problem
Description 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). Input 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). Output 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. Sample Input 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 Sample Output 3 IMPOSSIBLE Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator