二轮day2 snake解题报告_第1页
二轮day2 snake解题报告_第2页
二轮day2 snake解题报告_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

其实就是给定一幅地图，有，移动时间根据位置不同而不同（但这题难度不大，主要选手对BFS的运用能力，对时间、空间的优BFS，首先要设计好状态。对于此题，显然，蛇的位置要的，蛇的形态也是要的。由于不是单一位置作为目标，而是有多个食物，所以食物的存在情况也是要的。跟一般的BFS题目相比，此题还有一个特别的条件，就是移动的时间代价不一定是1。单纯这样想，似乎BFS就不可做了。但是，问题可以稍时间，这样的话，可以使得状态转移的代价仍为1，就可以使用BFS了。这样，需要再下等候时间这个信息。整条蛇的位置也就确定了。蛇头的位置有151544344334、5、6、74(3233343514402416间可能有8种，所以总状态数是225∗1440∗16∗8 这里有一个细节问题，就是蛇长为8的形态不需要统计，因为那必然可以知道，蛇的形态，只要保证不自交即可。是否自交，也只跟原始形态以及方向有关，跟位置无关，所以，主过程中完全不必要处理蛇的形态。并且，在不同位置不同的食物状态、等候时间，同一种形态变换结果是一样的，可以预先把所有蛇的形态变换预处理出来，并在主过程中以标号代替状态压缩，节省时间和空间。在预处理过程中，同样使用BFS。不同的形态在队列中出现的位置是如何转移的。对于1440种形态（根据程序计算的结果，实质只有种），每种形态记录下向4个方向和向4个方向进食后的状态编号即首先要准确计算，总状态数应该是225∗1200∗16∗8= 约是35M。35M的状态总数，但是队列需要记录的信息众多，需要很谨慎地使用空间，才能避免MLE。蛇头的两个坐标各需1个字节，形态记21个字节，状态转移的前驱需410350MB内存，加上判重需要35MB400MB的内存使用了。如果写程序的时候一时爽，全部intPascalrecodeMLE。所以必须小 程序的做法，大概就是，把前6个字节的信息用一个二进制压缩掉，剩下27位，可以用4个字节起来。1个字节8个二进制位，只用来一个bool有点浪费，就用位运算拆开8个使用好了，通过以上，可以把总内存控制在300MB左右其实有个小，可以发现实际的状态数是没有那么多的，那么……存不够用的时候把队列开小一点通常也是可行的。本来打算卡空间的，结果发现压缩也不是能节省特别多的内存，于是就没有特意卡了。POJ1324，不过经过

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论