主题:[讨论]最有挑战性的题目——有解就加30
[em10][em10][em10][em10][em10][em10][em10][em10][em10][em10][em10][em10][em10神奇的鞋
某一天,当贝茜在干草堆上蹭痒时,她发现草堆里有4只奇特的鞋子!穿上它们后,贝茜发现在这神奇的鞋子的帮助下,她能轻易地从牧场上的某块土地跳到另一块上。牧场的土地被划分成了R行(1<=R<=50)C列(1<=C<=50)。并且,这双鞋有2种不同的移动规则:或者是象国际象棋里的骑士一样跳跃,或者是另一种贝茜从未见过的跳跃方式:虽然还是向东南西北四个方向移动,但每次能移动2格。并且贝茜发现,在奇数步移动(也就是她的第1、3、5...次跳跃)时,鞋子遵循骑士的移动规则,而在偶数步移动时,鞋子会按上述的那种奇怪的规则来移动。
下面的图能帮助你更好地理解两种移动的规则:
骑士规则 (奇数步移动) 特殊规则 (偶数步移动)
. . K . K . . . . . O . . .
. K . . . K . . . . . . . .
. . . B . . . . O . B . O .
. K . . . K . . . . . . . .
. . K . K . . . . . O . . .
如果某一时刻贝茜在位置'B',那么在她的所有奇数步的移动时,她能移动到8个'K'中任意一个的位置上。如果她当前移动的步数为偶数,那在她这次移动结束后,她会在4个'O'中某一个的位置上。
在搞清楚了鞋子快速移动的规则后,贝茜决定继续自己刚才的计划:去糖果店与其他的奶牛会合。于是现在贝茜想知道,如果借助自己刚发现的神奇的鞋子,她在去糖果店的路径中至少要进行多少次移动。
现在你已经知道了牧场的大小以及贝茜、糖果店的位置。你的任务是,计算一下在这双神奇的鞋的帮助下,贝茜最少需要几次跳跃才能到达糖果店。当然,贝茜不能跳出牧场,但你可以认为她一定能找到一条去糖果店的路。
程序名: mcs
输入格式:
* 第1行: 包括2个用空格隔开的正整数,分别表示 R 和 C。
* 第2行: 贝茜的坐标,以2个用空格隔开的正整数表示她所在的行和列。
* 第3行: 糖果店的坐标,格式同第2行。
输入样例 (mcs.in):
4 5
4 1
4 3
输入说明:
. . . . .
. . . . .
. . . . .
B . C . .
输出格式:
* 第1行: 输出一个整数,表示在这神奇的鞋的帮助下,贝茜最少要跳跃多少次 才能到达糖果店。
输出样例 (mcs.out):
3
输出说明:
以下是一条可行的最短路径:
. . . . .
. 1 . 2 .
. . . . .
B . 3 . .
某一天,当贝茜在干草堆上蹭痒时,她发现草堆里有4只奇特的鞋子!穿上它们后,贝茜发现在这神奇的鞋子的帮助下,她能轻易地从牧场上的某块土地跳到另一块上。牧场的土地被划分成了R行(1<=R<=50)C列(1<=C<=50)。并且,这双鞋有2种不同的移动规则:或者是象国际象棋里的骑士一样跳跃,或者是另一种贝茜从未见过的跳跃方式:虽然还是向东南西北四个方向移动,但每次能移动2格。并且贝茜发现,在奇数步移动(也就是她的第1、3、5...次跳跃)时,鞋子遵循骑士的移动规则,而在偶数步移动时,鞋子会按上述的那种奇怪的规则来移动。
下面的图能帮助你更好地理解两种移动的规则:
骑士规则 (奇数步移动) 特殊规则 (偶数步移动)
. . K . K . . . . . O . . .
. K . . . K . . . . . . . .
. . . B . . . . O . B . O .
. K . . . K . . . . . . . .
. . K . K . . . . . O . . .
如果某一时刻贝茜在位置'B',那么在她的所有奇数步的移动时,她能移动到8个'K'中任意一个的位置上。如果她当前移动的步数为偶数,那在她这次移动结束后,她会在4个'O'中某一个的位置上。
在搞清楚了鞋子快速移动的规则后,贝茜决定继续自己刚才的计划:去糖果店与其他的奶牛会合。于是现在贝茜想知道,如果借助自己刚发现的神奇的鞋子,她在去糖果店的路径中至少要进行多少次移动。
现在你已经知道了牧场的大小以及贝茜、糖果店的位置。你的任务是,计算一下在这双神奇的鞋的帮助下,贝茜最少需要几次跳跃才能到达糖果店。当然,贝茜不能跳出牧场,但你可以认为她一定能找到一条去糖果店的路。
程序名: mcs
输入格式:
* 第1行: 包括2个用空格隔开的正整数,分别表示 R 和 C。
* 第2行: 贝茜的坐标,以2个用空格隔开的正整数表示她所在的行和列。
* 第3行: 糖果店的坐标,格式同第2行。
输入样例 (mcs.in):
4 5
4 1
4 3
输入说明:
. . . . .
. . . . .
. . . . .
B . C . .
输出格式:
* 第1行: 输出一个整数,表示在这神奇的鞋的帮助下,贝茜最少要跳跃多少次 才能到达糖果店。
输出样例 (mcs.out):
3
输出说明:
以下是一条可行的最短路径:
. . . . .
. 1 . 2 .
. . . . .
B . 3 . .