Chemfrog\'s Fairy Tale --CSDN问答

来自 : CSDN技术社区 发布时间：2021-03-25

私信 访问主页

编程介的小学生 2017-08-20 11:52 首页 Chemfrog\'s Fairy Tale numbers something each

Because of the evil wizard\'s curse, Chemfrog became a frog. Luckily, he met Cyjj. She told him that he could become a handsome boy again if he found the pretty princess and got her kiss. But the princess was captured by the evil wizard, and she was enjailed in the XiaoYingzhou in the West Lake.

Chemfrog bought a West Lake map. He found that the West Lake was in a regular shape as the picture1 shown below. So he marked the center of the lake to be (0, 0), and the northmost point to be (0, N), the southmost point to be (0, -N), the eastmost point to be (N, 0), the westmost point to be (-N, 0). Then he could marked the position of XiaoYingzhou with P(px, py).

picture 1: suppose N is 5

Time and tide wait for no one. Chemfrog jumped into the West Lake immediately, and went forward to P. When he arrived at the position (x0, y0), he felt something strange: he could not move freely! That\'s because the evil wizard detected his action and bewitched the West Lake. Chemfrog realized the problem soon, and he also found the jumping rule to fight against the bewitchery:

Rule 1: jumping like the Knight in Chess.
Rule 2: jumping without falling back.
Rule 3: jumping within the West Lake.

Picture 2 and Picture 3 show the Rules:

picture 2

picture 3

Note: if chemfrog jumped to the point marked blue from the yellow point, the next jump he could choose 5 point marked green, but the black ones and the yellow one were forbidden.

So Chemfrog jumped to (x1, y1) from (x0, y0). The evil wizard would not await his doom, and he flew to the West Lake to prevent Chemfrog to meet the princess. It\'s supposed that Chemfrog must jump onto the XiaoYingzhou within M jumps.

Is it possible for Chemfrog to meet the princess? Now it\'s turn for you to calculate whether Chemfrog could meet the pretty girl successfully. If it is possible, output the minimum number of jumping.

Input:

The input will consist of several test cases. The first line of each test case is two nonnegative number, said N (2 =N =500) and M (0 M =500). The second line contains six integer numbers: x0, y0, x1, y1, px, py. You may know that (x0, y0), (x1, y1), (px, py) are in the West Lake, and (x0, y0) won\'t equal to (px, py). N=M=0 signals the end of input file.

Output:

For each case, if Chemfrog could get to the XiaoYingzhou within M jumps, output the minimun number of jumping, otherwise output -1.

Sample Input:
7 5
1 2 2 4 0 0
7 3
1 2 2 4 0 0
2 10
-1 -1 0 1 0 0
0 0

Sample Output:
5
-1
-1

点赞 写回答 收藏 复制链接分享 删除 再等等 结题 再想想 1条回答

私信 访问主页

回答这么多问题就耍赖把我的积分一笔勾销了 4年前

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2631

点赞 评论 复制链接分享 提交 再想想 采纳 为你推荐 Chemfrog\'s Fairy Tale numbers 1个回答 点击登录 提问题 欢迎建议意见 . 如何写高质量提问和回答？ 采纳榜7天 被采纳次数 ProfSnail 25 幻灰龙 19 qq_34124780 154 coagenth 115 规则边缘 116 GoCityPass新加坡曼谷通票 117 cpp_learner 98 Jack_Yang(数据分析及可视化) 99 我不喜欢这个世界 810 天际的海浪 6 加急问题 500 500 基于tensorflow的模型做预测时，cpu占用率过高，如何降低程序的cpu占用率？ 100 unity 设置Animation的culling type 导致游戏崩溃 100 java实现下面两个算法 100 ECDSA加密算法中，签名和验证都是需要时间的，那其时间复杂度怎么用椭圆曲线参数如阶或模p来表示呢？ 75 数据库只有myd文件没有frm,myi文件，怎么打开呢 51 利用Adams联合matlab仿真求运动学反解问题 50 labview使用datasocket与c/c#程序的通信 50 python引用xlwings出问题，这个报错什么意思 ，怎么解决，谢谢大佬 50 如何用C语言实现凯撒密码对文本文件(.txt)的读取穷举暴力破解？ 50 已知地图GPS坐标点A和坐标点B，获取A点往B点直线走一定距离的坐标点经纬度？