编程C,C ++,Java,PHP,Ruby,图灵,VB
计算机科学加拿大 
编程C,C ++,Java,PHP,Ruby,图灵,VB  

用户名:   Password: 
 登记 登记    
 [CCC] 2002 S3蒙版
指数 -> 竞赛
查看上一个主题 可打印的版本下载主题订阅本主题私人信息刷新页面 查看下一个主题
作者 信息
SJ.




 邮政 发布: 2009年2月17日星期二7:37  发布主题:[CCC] 2002 S3蒙版

我正在浏览过去的比赛,并遇到了这个问题

引用:
S3J5
蒙住眼睛
罗斯和科林正在在他们的后院玩游戏。由于后院是矩形的
我们可以将其视为具有R行和C列的网格。玫瑰和科林障碍
一些正方形。
游戏的播放如下:
科林用眼罩覆盖了他的眼睛,然后玫瑰带来了他的一些网格广场
后院。她让他落下,以便他面对北,南,东部或西部。科林做了
不知道这个初始位置或方向。
然后玫瑰指示Colin使一系列M移动通过后院。每次搬家
是:F - 在他面临的方向上向前移动一个网格方形,
或者
l - 逆时针逆转90度,留在同一方形上,或
R - 顺时针旋转90度,留在同一方形上。
在进行这些动作之后,Colin站在一些最终位置。他现在必须是图
他站在哪里。您将通过编写程序来帮助他来确定所有
可能的最终位置。假设Colin的初始位置,最终位置和所有
中间位置位于后院内,但从未在一个包含的正方形中
障碍。您也可能假设Colin总是面临平行于的方向
后院的两侧(北,南,东部或西部)。
输入以R和C开头(1<= r <= 375; 1 <= c <= 80),每个单独的行。接下来是
描述后院的C字符线:一个句点字符表示网格方形
科林可以走路; x字符表示具有障碍物的网格正方形。
在网格下方是数字(0<= m <= 30000),然后是描述Colin的M线
移动。每行都有一个字符:f,l或r.
您的程序应输出后院网格,指示所有可能的最终位置
人物。
示例输入(输入文件:blind.in)
2
4
....
.xx。
3
F
R
F
样本输入输出(输出文件:盲目)
。* ..
.xx *


解决方案,如图所示 非官方解决方案网站 是纯粹的蛮力。即从每个广场开始,然后尝试移动列表。它通过所有测试数据,但数据都很小。地图上最多可以有30000个方格,高达30000的移动。显然,蛮力溶液将有足够好的测试用例。任何人都可以建议除蛮力之外更好的解决方案吗?
赞助
赞助
 赞助
 赞助
A.J.




 邮政 发布: 2009年2月17日星期二8:43  发布主题:RE:[CCC] 2002 S3蒙版

实际上,蛮力解决方案根本不会超时!

假设30000个方格都不是墙壁(即最坏的情况),那么时间复杂性仅仅是:
o(30000 * 4 * HeackyTime)
如果可以在每个位置遵循给定的方向,则在检查时间是在每个位置遵循的时间长度。

这并没有时光......我不认为我可以想到以外的任何方式......
OneOffdriveByposter.




 邮政 发布: 2009年2月17日星期二11:07 PM  发布主题:RE:[CCC] 2002 S3蒙版

蛮力仍有一个以上方式。

每个起始位置和方向的直接模拟是一种方式。

还可以从起始位置形成一组偏移到所有中间位置,最终位置和可能是起始位置本身 - 假设我们从“说”(0,0)开始,并且朝着方向前进这将导致我们带来“说”(0,1)。

上述集合可以让我们比直的SIM更好。根据定义,一组不包括两次相同的位置(尽管位置确实可能不止一次交叉,但我们只需要检查一次)。

尝试每个起始位置的列表(或者如果智能,我们可以跟踪左上角和右上右侧偏移和修剪)。

要尝试其他启动方向,可以旋转网格或列表。

可视化:创建透明度与布局的路径;将透明度移动到地图上并扫描以检查。旋转透明度或地图将实现相同的效果。

在直接SIM和预处理的偏移版本中,可能会在起始位置提前放弃。在预处理的版本中,跟踪“左上”和“右下方”允许某些启动位置丢弃蝙蝠。
A.J.




 邮政 发布: 2009年2月17日星期二11:28  发布主题:RE:[CCC] 2002 S3蒙版

嗯,在那种情况下,您也可以在每个步骤中DP,并具有“回溯”,以跟踪您遵循的某个点的“移动”(或方向),并看看是否与给定的一组方向匹配....

无论如何,这仍然围绕着同样的基本抨击

“......我不认为我可以想到以外的任何其他方式......”我的意思是我认为没有优雅的解决方案。
SJ.




 邮政 发布: 2009年2月18日星期三上午9:08  发布主题:RE:[CCC] 2002 S3蒙版

我刚刚尝试了最糟糕的情况,我可以想到,这需要大约125米米的操作。在大约4秒钟内跑 - 比我想象的要快得多!我猜蛮力会及时工作。

事实上,它是一个矩形网格真的限制了最坏的情况。

我认为更快的方式是,如果我们将地图存储为一个设置的数字,那么使用位模式我们可以确定当前的“透明度”是否适合或不在相当小的恒定时间内。

无论如何,谢谢你的回复!
Bugzpodder.




 邮政 发布: 2009年2月18日星期三11:22  发布主题:RE:[CCC] 2002 S3蒙版

认为我那年做了高级版本。

无论如何,一件事要加速它是只存储所有偏移(角落)以检查它是否仍然存在于迷宫中。然后在两个角落之间是一条直线,你可以检查它是否包含任何障碍物。
A.J.




 邮政 发布: 2009年2月18日星期三12:03 PM  发布主题:RE:[CCC] 2002 S3蒙版

是的,4秒落下麦克力(轻松)!

所以它有效。
从上一个显示帖子:   
    指数 -> 竞赛
查看上一个主题 告诉一个朋友可打印的版本下载主题订阅本主题私人信息刷新页面 查看下一个主题

11  [ 7 Posts ]
跳到:   


Style:  
搜索: