2011-0055
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
占by大肥羊。。
这题是纯粹的bfs，和我第一轮出的Alice Madness Return差不多，这种类型的题目就是算法很简单，但是规则比较复杂，bfs的时候一定要仔细，做之前先多读题，搞清楚题意再做，建议没有AC的童鞋可以把两题都做一做，对coding的锻炼还是很有帮助的
题目意思就是在m*n的格子里，麦香飞船从起点出发要飞到218所在的格子，每回合只能上下左右选择一步，迷宫里有些格子是'J'表示的，这个相当于传送阵，如果我踏入一个'J',那么就可以传送到很远的地方，但只能传我进入的方向，比如我踏进【我右边】的'J'，那么我就只能传送到这个'J'右边的【空地】，同时这个空地的【左边】必须也有一个'J'作为出口
举个例子
XJ....J..J..J
X代表飞船，在0号格子，这样他可以通过1号格子的J传送到6号'J'右边的7号空地，或者9号'J'右边的10号空地,但是不能传到12号J右边，因为没有13号格子
另外3个方向也是类似的
此外，迷宫还有一个海盗飞船，海盗是做周期运动的，每回合也是只移动一个格子，首先朝上飞，如果飞到边界了，那么就掉头，下一回合就往下飞，飞回起始点之后海盗就要调转方向，转为向左飞，然后重复之前的走法，也就是说海盗会在上左下右四个方向上做往返运动，每次到地图边界就飞回起始点，到起始点就改变大方向
如果麦香飞船和海盗在同一直线上并且中间没有J，那么麦香会被劫持，任务失败~每回合两个飞船都是同时移动的，所以可以在他们移动结束后再判断是否在一条直线上
另外题目规定刚开始的时候（即时间为0的时候）以及麦香到达218的格子的时候，海盗无法攻击麦香
现在要求麦香的最短到达时间，那么直接bfs就好了，状态为40*40*40*40,分别表示麦香和海盗的位置，其实可以用40*40*160，这个160就是海盗飞行的最大周期，直接用周期代替海盗的坐标可以加快速度
最后题目的描述有点问题，题目描述里说了“Please note that both the Jump Equipments and the other crafts may occupy the planet and makes it unavailable for the delivery craft”，也就是说麦香和海盗不能重叠在一个格子，但是题目的数据里有一种情况是麦香和海盗重叠在218了，而标程认为这种情况是合法的，所以如果你wa到死，应该检查一下是不是把这个弄成不合法了占by大肥羊。。
这题是纯粹的bfs，和我第一轮出的Alice Madness Return差不多，这种类型的题目就是算法很简单，但是规则比较复杂，bfs的时候一定要仔细，做之前先多读题，搞清楚题意再做，建议没有AC的童鞋可以把两题都做一做，对coding的锻炼还是很有帮助的
题目意思就是在m*n的格子里，麦香飞船从起点出发要飞到218所在的格子，每回合只能上下左右选择一步，迷宫里有些格子是'J'表示的，这个相当于传送阵，如果我踏入一个'J',那么就可以传送到很远的地方，但只能传我进入的方向，比如我踏进【我右边】的'J'，那么我就只能传送到这个'J'右边的【空地】，同时这个空地的【左边】必须也有一个'J'作为出口
举个例子
XJ....J..J..J
X代表飞船，在0号格子，这样他可以通过1号格子的J传送到6号'J'右边的7号空地，或者9号'J'右边的10号空地,但是不能传到12号J右边，因为没有13号格子
另外3个方向也是类似的
此外，迷宫还有一个海盗飞船，海盗是做周期运动的，每回合也是只移动一个格子，首先朝上飞，如果飞到边界了，那么就掉头，下一回合就往下飞，飞回起始点之后海盗就要调转方向，转为向左飞，然后重复之前的走法，也就是说海盗会在上左下右四个方向上做往返运动，每次到地图边界就飞回起始点，到起始点就改变大方向
如果麦香飞船和海盗在同一直线上并且中间没有J，那么麦香会被劫持，任务失败~每回合两个飞船都是同时移动的，所以可以在他们移动结束后再判断是否在一条直线上
另外题目规定刚开始的时候（即时间为0的时候）以及麦香到达218的格子的时候，海盗无法攻击麦香
现在要求麦香的最短到达时间，那么直接bfs就好了，状态为40*40*40*40,分别表示麦香和海盗的位置，其实可以用40*40*160，这个160就是海盗飞行的最大周期，直接用周期代替海盗的坐标可以加快速度
最后题目的描述有点问题，题目描述里说了“Please note that both the Jump Equipments and the other crafts may occupy the planet and makes it unavailable for the delivery craft”，也就是说麦香和海盗不能重叠在一个格子，但是题目的数据里有一种情况是麦香和海盗重叠在218了，而标程认为这种情况是合法的，所以如果你wa到死，应该检查一下是不是把这个弄成不合法了