【寒假作业】【NOIP2013】华容道

这题太可啪了。。

不过高兴的是一遍就A了XD

首先一个显而易见的事情就是 这题可以写BFS

于是你就可以获得60分的高分了!

然后恭喜你!2013年HN一等线300分!你应该有一等了!

【但是我们要AK!

那么这道题怎么A呢?

我们先分析一下这道题:可以发现,每一次询问的棋盘都是一样的;而且这个棋盘长最大为30。

我们的目的是:通过空格将一个棋子移动到另一个地方

我们可以把这个过程分解为:每次利用空格每次将这个棋子移动一步

那么总共的决策就有两种了:

  1. 把空格从棋子的某个方向移动到棋子的另一个方向
  2. 把棋子移入空格

那么我们先对这个棋盘进行一下预处理!记录在某个点(x,y)周围,一个空格移动到另一个位置的最短距离(方便决策1)【O(n^4)】

然后对于每次询问,就可以SPFA了!

第一步先将空格移到初始棋子四周作为4个初始状态,然后就只有那两种决策了!

【感觉我的代码对比别人的还是很短的。。只有120行。。

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz