回 帖 发 新 帖 刷新版面

主题:[讨论]最有挑战性的题目——有解就加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 . .

回复列表 (共14个回复)

沙发


看不懂

板凳

我觉得就是
双向广搜
只不过是奇数步和偶数步的移动规则不同

3 楼

强烈同意2楼的说法 具体一点就是把双广中原本每次扩展一层改为每次扩展两层 而判断成功也需从这两层中判断 题目本身不是太难 不过结合双广的输入量 我认为这道题需要相当的耐心 数据规模并不大 用普通数组就可以

4 楼

同意二楼的说法
就是奇数步的走法和偶数步的走法不同
所以造成了这样的广搜问题。

5 楼

有测试数据吗?

6 楼

我不懂

7 楼

难呀!我的水平还没有到这里.

8 楼

实在是不理解,谁说得清楚点?

9 楼

看完后差一點沒暈

10 楼

双向广度搜索,只不过太难

我来回复

您尚未登录,请登录后再回复。点此登录或注册