USACO 玉米田迷宫 Corn Maze

这题是一个大坑。

首先我们想到了BFS,这个题就是一个简单到不能再简单的Maze加上传送门就是了。

但是有一点是传送门不费时啊!!什么鬼。所以我们要先判传送门

为什么呢?我记得有一组测试数据包括了这种情况

 

这不清真

另外,好像还有一个点是全都是传送门的情况。

 

 

这也不清真

 

判传送门(并不是判队首元素位于传送门,而是队首坐标移动之后),传送过去之后耗时不加,队列保存传送后的位置,这样就不会产生无限传送死循环的问题。

但是关于情况2怎么办?我们利用BFS的性质,把传送门(传过去之后)打上标记,然后就不用他了。(每一次用都是最早用他)

传送门I hate you

 

读入的时候记录传送门的相对坐标,像这样:

 

之后碰到传送门直接查表。,顺便记下起点sxsy和重点exey

 

 

其实这个题处理好了传送门,你会发现,其实不难……(输出调试大法好)

记得用checked数组标记已经访问的点和传送门,要不无限使用传送门

 

“USACO 玉米田迷宫 Corn Maze”的一个回复

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据