| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 426 人关注过本帖
标题:[求助]梦游者问题
只看楼主 加入收藏
芦苇six
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2006-7-13
收藏
 问题点数:0 回复次数:3 
[求助]梦游者问题

老师给我们出了道奥赛的题目,不会编啊,我连题目都看不大明白,请高手指点!
问题描述
在一幢豪华的公寓中,有一块面积巨大的正方形大厅。这个大厅的地板被分成了3k×3k个格子,每个格子上都被铺了一块与格子面积大小一致的瓷砖,如此的布置使得整个大厅显得更加的气派。遗憾的是,地板上有一块瓷砖因为损坏而被移走了,这就留下了一个洞。
为了方便的表示这个洞的位置,我们将大厅的地板置于一个平面直角坐标系中,最西南方的格子的坐标为(1,1),往东是X轴的正方向,往北是Y轴的正方向。
一个梦游者正在这个大厅里游荡。梦游者从西南方(1,1)出发,每次可以往四周的方向(东E、南S、西W、北N)移动,要走便所有的格子而不重复。他的行动路线十分怪异,例如k=1,即地板是3×3规模时,他的行走路线为:D1=EENNWSWN;当k=2时,地板是9×9规模,他的行走路线D2=NNEESWSEENNEESWSEEEENNWSWNNEENNWSWNNEENNWSWNWWWSSENESSSSWWNENWWSSWWNENWNEENNWSWN。
直观的将路线画在图上如图:
总的来说,当地板规模是3k+1×3k+1时,梦游者的路径为
Dk+1 = a(Dk) E a(Dk) E Dk N Dk N Dk W c(Dk) S b(Dk) W b(Dk) N Dk
其中,a(),b(),c()均表示一种字母置换,具体如下:
a: E->N W->S N->E S->W
b: E->S W->N N->W S->E
c: E->W W->E N->S S->N
例如,a(SEN)=WNE, b(SEN)=ESW, c(SEN)=NWS
现在,梦游者正站在坐标为(x1,y1)的地板上,而没有因为瓷砖损坏造成了一个洞的地板坐标为(x2,y2)。你能求出可怜的梦游者将在第几步后跌入洞中么?
输入文件
输入文件名:LUN.IN
第一行有一个数字k(1<=k<=60),表示大厅地板的规模是3k×3k。
第二行有两个数字,x1和y1表示梦游者L先生开始所站的坐标位置。
第三行有两个数字,x2和y2表示洞的坐标位置。
可以保证的是梦游者在若干步之后一定会跌入洞中。

输出文件
输出文件名:LUN.OUT
输出文件只有一行,一个数字,表示多少步后,梦游者会跌如洞中。

样例输入
2
3 2
7 2

样例输出
20

图片附件: 游客没有浏览图片的权限,请 登录注册

搜索更多相关主题的帖子: 梦游 
2006-07-13 19:22
污秽摇篮
Rank: 1
等 级:新手上路
帖 子:1259
专家分:0
注 册:2006-1-10
收藏
得分:0 
看题目看的就头晕

那天是你用一块红布,蒙住了我双眼也蒙住了天.
你问我看见了什么,我说我看见了幸福......
2006-07-13 20:19
豆浆GG
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2006-7-14
收藏
得分:0 

我们老师都不会做55555


你就是马甲,马甲就是你,我能咋地?
2006-07-14 18:32
abcqsqsabc
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2006-7-15
收藏
得分:0 

D1是3×3的路线,D2是9×9的路线,这个看的懂吧?
再理解一点就是D2的路线是由 9个D1(方向不同)组合出来的
同理Dk的路线是由Dk-1 组合出来的,当给定一个k,就能直接用递归做出从左下入口到右上出口的路线了
有了路线再算洞的位置到梦游者的位置要几步就好算了

至于这9个Dk-1方向不同的子路线,通过字母变换
a: E->N W->S N->E S->W
b: E->S W->N N->W S->E
c: E->W W->E N->S S->N 就能实现
题目也告诉你 9个Dk-1 需要哪一种变换方式了
具体程序自己实现吧

2006-07-15 23:11
快速回复:[求助]梦游者问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.016301 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved