最新消息:380元/半年,推荐全网最具性价比的一站式编程学习平台码丁实验室

信息学奥赛题库- 棋盘问题

C++ 少儿编程 1290浏览 0评论

友情提示:380元/半年,儿童学编程,就上码丁实验室

【题目描述】

在一个无限大的棋盘上给定起点($f_x,f_y$)和终点坐标($t_x,t_y$),再给定$n$个向量,每个向量形如($x,y$),表示当前点在($a,b$)时可以一步走到($a+x,b+y$)。求从起点出发到达终点的最小步数。

【输入】

第一行一个整数$T$,表示共有$T$组数据。

对于每组数据:

第一行四个整数$f_x,f_y,t_x,t_y$,表示起点终点坐标。

第二行一个整数$n$,表示可走的方向有$n$个。

接下来n行每行两个整数$x,y$,表示一个向量($x,y$)。

【输出】

若有可行的方案,输出一行一个整数$ans$,表示最小步数。

否则输出“IMPOSSIBLE”。

【输入样例】

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

【提示】

【数据规模与约定】

对于100%的数据,$T<20,-5000≤f_x,f_y,t_x,t_y≤5000,1≤n≤10,1≤x,y≤10$。

您必须 登录 才能发表评论!