公主迷宫冒险小游戏,在线玩,4399小游戏
合理操作，帮助公主完成各项任务！
游戏加载完毕点击两次PLAY - 接着点击左上方的图片 - 然后点击PLAY即可开始游戏
你可能喜欢的游戏
如果觉得4399小游戏好玩，请把
告诉你的朋友！更好玩的游戏等着你！
方向键↑↓←→控制移动。
游戏加载完毕点击两次PLAY - 接着点击左上方的图片 - 然后点击PLAY即可开始游戏
公主的宝物被抛弃在了迷宫里，现在她要出发去迷宫里将失去的宝物全都找回来，她能做到吗？快去看看吧！
合理操作，帮助公主完成各项任务！
多人在线小游戏
|||||||||||||||
作品版权归作者所有，如果侵犯了您的版权，请，本站将在3个工作日内删除。温馨提示：抵制不良游戏，拒绝盗版游戏，注意自我保护，谨防受骗上当，适度游戏益脑，沉迷游戏伤身，合理安排时间，享受健康生活
||||||&关注：
||||&法律顾问：北京盛峰律师事务所
文明办网文明上网举报电话：&|&举报邮箱：&||
Copyright & 2004 -
All Rights Reserved. 四三九九网络股份有限公司 版权所有勇士救公主小游戏,勇士救公主小游戏在线玩,勇士救公主小游戏下载,17173小游戏
您当前所在位置：&>&勇士救公主
勇士救公主
点击，方便下次再玩。 《勇士救公主》小游戏由17173用户提供。
小游戏评分 ：
( 得分: 分 )
勇士救公主
操作说明：
玩家1：键选择石头剪刀布；
玩家2：键选择石头剪子布。
勇士救公主:一群山贼再次来到城堡之中掠夺啦，这次他们不仅抢走了珠宝，还将城堡中那最美丽的公主也给掳走了，听到这个消息后，我们小勇士立刻拔剑而起追了上去，可是他能否击败山贼救出公主呢？我们赶紧去帮帮他吧！游戏中的对战方式就是我们常玩的剪刀石头布，现在就赶快进入游戏中，看准对手说出的手势，然后给它们沉重的一击吧！游戏还支持双人对战模式哦~倘若你觉得自己玩厌了，还可以叫上你的小伙伴与你较量一番。
如何开始:加载完毕点击Start - 再点击右边的任意一个NEW GAME按钮 - 接着点击中间的箭头选择模式(闯关/单人/双人) - 然后点击两个人物下方的pick再点击右下方的勾即可开始游戏
喜欢玩《勇士救公主》的小伙伴们，可以收藏起来下次再玩哦~！！
大小：14.62M
操作说明：
玩家1：键选择石头剪刀布；
玩家2：键选择石头剪子布。
勇士救公主:一群山贼再次来到城堡之中掠夺啦，这次他们不仅抢走了珠宝，还将城堡中那最美丽的公主也给掳走了，听到这个消息后，我们小勇士立刻拔剑而起追了上去，可是他能否击败山贼救出公主呢？我们赶紧去帮帮他吧！游戏中的对战方式就是我们常玩的剪刀石头布，现在就赶快进入游戏中，看准对手说出的手势，然后给它们沉重的一击吧！游戏还支持双人对战模式哦~倘若你觉得自己玩厌了，还可以叫上你的小伙伴与你较量一番。
如何开始:加载完毕点击Start - 再点击右边的任意一个NEW GAME按钮 - 接着点击中间的箭头选择模式(闯关/单人/双人) - 然后点击两个人物下方的pick再点击右下方的勾即可开始游戏
热门好评小游戏
玩过《勇士救公主》的玩家推荐玩
玩过《勇士救公主》的玩家还玩过
热门小游戏合集
热门单机合集下载
原创小游戏推荐
新游看世界
看完这篇新闻有何感觉？已经有0人表态
正在接收数据...
大家都在玩的小游戏
我的世界放置中文
人气：334558
金庸群侠传x1.0
人气：165880
死神VS火影2.4
人气：137344
死神VS火影2.3
人气：108719
僵尸点击中文版
人气：90159
金庸群侠传x0.9(
人气：76642
索菲亚生六胞胎
人气：75727
末日危机2升级版
人气：69339
艾莎的时尚商店
人气：61647
史上最贱小游戏13
人气：60960
人气：58362
珍珠美人鱼公主
人气：52974
异形挂机战中文版
人气：52953
核反应堆放置中文
人气：51442
无尽的DPS中文版
人气：49127
老爹三明治店无敌
人气：48197
大海贼时代2中文
人气：44437
无限挖矿中文版
人气：44221
挂机进化中文版
人气：44163
点击亡灵挂机
人气：43983
索菲亚公主做手术
人气：41733
朱丽叶公主逃离博
人气：39497
人气：39356
次元树之战V2.10
人气：38277
超级病原体
人气：38055
我的世界放置
人气：37971
人气：37596
芭比宝贝溺水了
人气：37493
艾莎食物中毒治疗
人气：37206
剑士之魂中文版
人气：36901
点击冒险(Tap Adventure
人气：36134
人气：34393
超级玛丽经典版
人气：34331
忍者的宿命中文版
人气：34085
猜歌王之EXO2
人气：32383
黑市V1.2中文版
人气：32037
商业帝国3中文版
人气：31911
化学增量中文版
人气：31883
皇城攻防战2
人气：31583
老爹三明治店中文
人气：31532
朵拉制作纸杯蛋糕
人气：31074
索菲亚公主的爱情
人气：30924
战火英雄3无敌版
人气：30248
玩具城堡无敌版
人气：29316
经营货运公司3中
人气：29302
孤岛殖民地中文版
人气：28748
勇者之旅电脑版
人气：28497
中土传奇中文版
人气：28064
妖尾VS海贼王0.9
人气：28031
绿色王国之战中文
人气：27850
开垦与发展中文版
人气：27657
格鲁夫村的守护者
人气：27215
人鱼公主做产检
人气：26815
皇城战士中文版
人气：26627
炉石挂机中文版
人气：26491
女神任务2中文版
人气：26469
人气：26417
僵尸点击升级版(
人气：25834
竞技场之神中文版
人气：25676
六角消除Hex FRVR
人气：25588
小游戏月排行迷宫小游戏大全
游戏简介：最好玩的迷宫小游戏、迷宫小游戏大全，尽在新浪玩玩小游戏平台。这里不仅有走迷宫小游戏，还有数以千计、五花八门的免费在线小游戏等你来玩，还等什么！快来玩吧！
迷宫小游戏
热门游戏榜
新浪玩玩意见反馈
欢迎使用新浪玩玩并提出宝贵建议。请提交玩玩意见反馈。
Copyright & 1996 - 2016 SINA Corporation, All Rights Reserved
北京市通信公司提供网络带宽有一个闯关的游戏，里面是王子（骑士）走迷宫拿宝物救公主，有个道具是钉子鞋，好几年前的游戏了，求游戏_百度知道
有一个闯关的游戏，里面是王子（骑士）走迷宫拿宝物救公主，有个道具是钉子鞋，好几年前的游戏了，求游戏
大约是五六年前得了
我找到了，是魔王迷宫……
提问者采纳
但忘了有点印象，有个雷达一样的东东 。宝物拿齐才行
提问者评价
其他类似问题
为您推荐：
走迷宫的相关知识
其他1条回答
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁营救公主(Java实现A*算法解决迷宫问题)
很早就听说过A*算法，据说在寻路径时，是一种比较高效的算法。但是一直没有搞清楚原理。
这段时间刚好有个营救公主的例子：
公主被魔王抓走了 ， 王子需要拯救出美丽的公主 。 他进入了魔王的城
堡 ， 魔王的城堡是一座很大的迷宫 。 为了使问题简单化 ， 我们假设这个迷宫是一
个 N*M 的二维方格 。 迷宫里有一些墙 ， 王子不能通过 。 王子只能移动到相邻 （ 上
下左右四个方向 ) 的方格内 ， 并且一秒只能移动一步 ， 就是说 ， 如果王子在 (x,y ）
一步只能移动到 (x-1,y),(x+1,y),(x,y-1),(x,y+1) 其中的一个位置上。地图由
&S&，&P&，& . & ， & *& 四种符号构成 ， & . & 表示王子可以通过 ， & *& 表示
墙，王子不能通过；'S'表示王子的位置；&P&表示公主的位置； n表示公主存活的剩余时间，王子必须在 n 秒
内到达公主的位置，才能救活公主。
解题思路：
1、可以通过广度优先的算法进行演进，不停的查找王子的所有下一点的位置，没查找一次时间减1，直到找到了公主或者时间为0时终止。
这个算法能够比较快速的解决上述的迷宫问题；
2、通过A*算法，查找出每次移动可能到达的所有点，并设置了一定的权值规则，每次选取权值最小的一个点找它的下一个点&&(当然，这是搞懂原理之后的后话:) )
本着锻炼下自己的原则选择了A*算法解决上面的问题。
&代码实现简要说明：
1、定义了一个迷宫类 Maze，迷宫中包含了王子Prince（包含核心算法）和迷宫的地图MazeMap，迷宫（游戏）启动时，会先初始化地图，然后王子开始寻路（具体算法看代码）;
2、定义了一个位置类Position，描述了二维坐标信息，及加权的PositionWeight类，包含了位置信息、距离王子的距离（A*算法中的G）、距离公主的距离（A*算法中的H）、及二者的总开销(F=G+H)；
相信看懂了A*算法的原理的朋友，很快就能写出一个迷宫的实现方案。
下面贴一下我的实现，注释还算比较详尽，欢迎批评指正:)
&* 迷宫中的位置点 创建人：dobuy
public class Position&
&&&& * 水平或者垂直移动一格的距离
&&& private final static int STRAIGHT_DISTANCE = 10;&
&&&& * 对角线移动一格的距离
&&& private final static int DIAGONAL_LINE_DISTANCE = 14;&
&&& public Position(int x, int y)&
&&&&&&& super();&
&&&&&&& this.x =&
&&&&&&& this.y =&
&&&& * 获取从父节点直接偏移至子节点的距离
&&& public int getOffsetOfDistance(Position position)&
&&&&&&& int x = Math.abs(getX() - position.getX());&
&&&&&&& int y = Math.abs(getY() - position.getY());&
&&&&&&& Position offset = new Position(x, y);&
&&&&&&& if (offset.equals(new Position(0, 1))&
&&&&&&&&&&&&&&& || offset.equals(new Position(1, 0)))&
&&&&&&& {&
&&&&&&&&&&& return STRAIGHT_DISTANCE;&
&&&&&&& }&
&&&&&&& return DIAGONAL_LINE_DISTANCE;&
&&&& * 获取到目标节点的平移距离
&&& public int getDistanceOfTarget(Position position)&
&&&&&&& int verticalDistance = Math.abs(getY() - position.getY());&
&&&&&&& int horizontalDistance = Math.abs(getX() - position.getX());&
&&&&&&& return (verticalDistance + horizontalDistance) * STRAIGHT_DISTANCE;&
&&& public Position offset(Position offset)&
&&&&&&& return new Position(getX() + offset.getX(), getY() + offset.getY());&
&&& public int getX()&
&&& public void setX(int x)&
&&&&&&& this.x =&
&&& public int getY()&
&&& public void setY(int y)&
&&&&&&& this.y =&
&&& @Override&
&&& public int hashCode()&
&&&&&&& final int prime = 31;&
&&&&&&& int result = 1;&
&&&&&&& result = prime * result +&
&&&&&&& result = prime * result +&
&&& @Override&
&&& public boolean equals(Object obj)&
&&&&&&& if (this == obj)&
&&&&&&&&&&&&
&&&&&&& if (obj == null)&
&&&&&&&&&&&&
&&&&&&& if (getClass() != obj.getClass())&
&&&&&&&&&&&&
&&&&&&& Position other = (Position)&
&&&&&&& if (x != other.x)&
&&&&&&&&&&&&
&&&&&&& if (y != other.y)&
&&&&&&&&&&&&
&&& @Override&
&&& public String toString()&
&&&&&&& return &Position [x=& + x + &, y=& + y + &]&;&
&* 迷宫中的位置点 创建人：dobuy
public class Position
& * 水平或者垂直移动一格的距离
&private final static int STRAIGHT_DISTANCE = 10;
& * 对角线移动一格的距离
&private final static int DIAGONAL_LINE_DISTANCE = 14;
&public Position(int x, int y)
&&super();
&&this.x =
&&this.y =
& * 获取从父节点直接偏移至子节点的距离
&public int getOffsetOfDistance(Position position)
&&int x = Math.abs(getX() - position.getX());
&&int y = Math.abs(getY() - position.getY());
&&Position offset = new Position(x, y);
&&if (offset.equals(new Position(0, 1))
&&&&|| offset.equals(new Position(1, 0)))
&&&return STRAIGHT_DISTANCE;
&&return DIAGONAL_LINE_DISTANCE;
& * 获取到目标节点的平移距离
&public int getDistanceOfTarget(Position position)
&&int verticalDistance = Math.abs(getY() - position.getY());
&&int horizontalDistance = Math.abs(getX() - position.getX());
&&return (verticalDistance + horizontalDistance) * STRAIGHT_DISTANCE;
&public Position offset(Position offset)
&&return new Position(getX() + offset.getX(), getY() + offset.getY());
&public int getX()
&public void setX(int x)
&&this.x =
&public int getY()
&public void setY(int y)
&&this.y =
&@Override
&public int hashCode()
&&final int prime = 31;
&&int result = 1;
&&result = prime * result +
&&result = prime * result +
&@Override
&public boolean equals(Object obj)
&&if (this == obj)
&&if (obj == null)
&&if (getClass() != obj.getClass())
&&Position other = (Position)
&&if (x != other.x)
&&if (y != other.y)
&@Override
&public String toString()
&&return &Position [x=& + x + &, y=& + y + &]&;
&* 位置信息的权值
public class PositionWeight&
&&&& * 水平或者垂直移动一格的距离
&&& private final static int STRAIGHT_DISTANCE = 10;&
&&&& * 当前的位置信息
&&& private P&
&&&& * 起始点（王子的起始位置），经由当前点的父节点后，到当前点的距离(仅包括垂直和水平直线上的)
&&& private int distanceOfP&
&&&& * 当前点到目标点（公主位置）的距离
&&& private int distanceOfP&
&&&& * 父节点的权值
&&& private PositionW&
&&&& * 总开销：包括起始点到当前点和当前点到终点的开销之和
&&& public PositionWeight(Position position)&
&&&&&&& this.position =&
&&& public PositionWeight(Position position, PositionWeight father,&
&&&&&&&&&&& PositionWeight target)&
&&&&&&& this(position);&
&&&&&&& countDistanceToTarget(target);&
&&&&&&& updateByFather(father);&
&&&& * 获取父子节点间的距离:对角线为14,水平、垂直为10
&&& public int getDistanceFromAttemptFather(PositionWeight father)&
&&&&&&& Position fatherPosition = father.getPosition();&
&&&&&&& return fatherPosition.getOffsetOfDistance(getPosition());&
&&&& * 更新父节点，并设置当前点的权值
&&& public void updateByFather(PositionWeight father)&
&&&&&&& setFather(father);&
&&&&&&& int distanceOfPrince = getDistanceFromAttemptFather(father);&
&&&&&&& setDistanceOfPrince(distanceOfPrince + father.getDistanceOfPrince());&
&&&&&&& setCost(getDistanceOfPrince() + getDistanceOfPrincess());&
&&& public Position getPosition()&
&&& public PositionWeight getFather()&
&&& public int getCost()&
&&& public int getDistanceOfPrince()&
&&&&&&& return distanceOfP&
&&&& * 获取花费的总开销
&&& public int getSpendTime()&
&&&&&&& return getCost() / STRAIGHT_DISTANCE;&
&&& @Override&
&&& public int hashCode()&
&&&&&&& final int prime = 31;&
&&&&&&& int result = 1;&
&&&&&&& result = prime * result&
&&&&&&&&&&&&&&& + ((position == null) ? 0 : position.hashCode());&
&&& @Override&
&&& public boolean equals(Object obj)&
&&&&&&& if (this == obj)&
&&&&&&&&&&&&
&&&&&&& if (obj == null)&
&&&&&&&&&&&&
&&&&&&& if (getClass() != obj.getClass())&
&&&&&&&&&&&&
&&&&&&& PositionWeight other = (PositionWeight)&
&&&&&&& if (position == null)&
&&&&&&& {&
&&&&&&&&&&& if (other.position != null)&
&&&&&&&&&&&&&&&&
&&&&&&& }&
&&&&&&& else&
&&&&&&&&&&& if (!position.equals(other.position))&
&&&&&&&&&&&&&&&&
&&& @Override&
&&& public String toString()&
&&&&&&& return &PositionWeight [position=& + position + &, distanceOfPrince=&&
&&&&&&&&&&&&&&& + distanceOfPrince + &, distanceOfPrincess=&&
&&&&&&&&&&&&&&& + distanceOfPrincess + &, father=& + father.getPosition()&
&&&&&&&&&&&&&&& + &, cost=& + cost + &]&;&
&&&& * 设置到目标节点的距离
&&& private void countDistanceToTarget(PositionWeight target)&
&&&&&&& Position targetPosition = target.getPosition();&
&&&&&&& int distanceToTarget = getPosition()&
&&&&&&&&&&&&&&& .getDistanceOfTarget(targetPosition);&
&&&&&&& setDistanceOfPrincess(distanceToTarget);&
&&& private void setDistanceOfPrince(int distanceOfPrince)&
&&&&&&& this.distanceOfPrince = distanceOfP&
&&& private int getDistanceOfPrincess()&
&&&&&&& return distanceOfP&
&&& private void setDistanceOfPrincess(int distanceOfPrincess)&
&&&&&&& this.distanceOfPrincess = distanceOfP&
&&& private void setFather(PositionWeight father)&
&&&&&&& this.father =&
&&& private void setCost(int cost)&
&&&&&&& this.cost =&
&* 位置信息的权值
public class PositionWeight
& * 水平或者垂直移动一格的距离
&private final static int STRAIGHT_DISTANCE = 10;
& * 当前的位置信息
&private P
& * 起始点（王子的起始位置），经由当前点的父节点后，到当前点的距离(仅包括垂直和水平直线上的)
&private int distanceOfP
& * 当前点到目标点（公主位置）的距离
&private int distanceOfP
& * 父节点的权值
&private PositionW
& * 总开销：包括起始点到当前点和当前点到终点的开销之和
&public PositionWeight(Position position)
&&this.position =
&public PositionWeight(Position position, PositionWeight father,
&&&PositionWeight target)
&&this(position);
&&countDistanceToTarget(target);
&&updateByFather(father);
& * 获取父子节点间的距离:对角线为14,水平、垂直为10
&public int getDistanceFromAttemptFather(PositionWeight father)
&&Position fatherPosition = father.getPosition();
&&return fatherPosition.getOffsetOfDistance(getPosition());
& * 更新父节点，并设置当前点的权值
&public void updateByFather(PositionWeight father)
&&setFather(father);
&&int distanceOfPrince = getDistanceFromAttemptFather(father);
&&setDistanceOfPrince(distanceOfPrince + father.getDistanceOfPrince());
&&setCost(getDistanceOfPrince() + getDistanceOfPrincess());
&public Position getPosition()
&public PositionWeight getFather()
&public int getCost()
&public int getDistanceOfPrince()
&&return distanceOfP
& * 获取花费的总开销
&public int getSpendTime()
&&return getCost() / STRAIGHT_DISTANCE;
&@Override
&public int hashCode()
&&final int prime = 31;
&&int result = 1;
&&result = prime * result
&&&&+ ((position == null) ? 0 : position.hashCode());
&@Override
&public boolean equals(Object obj)
&&if (this == obj)
&&if (obj == null)
&&if (getClass() != obj.getClass())
&&PositionWeight other = (PositionWeight)
&&if (position == null)
&&&if (other.position != null)
&&&if (!position.equals(other.position))
&@Override
&public String toString()
&&return &PositionWeight [position=& + position + &, distanceOfPrince=&
&&&&+ distanceOfPrince + &, distanceOfPrincess=&
&&&&+ distanceOfPrincess + &, father=& + father.getPosition()
&&&&+ &, cost=& + cost + &]&;
& * 设置到目标节点的距离
&private void countDistanceToTarget(PositionWeight target)
&&Position targetPosition = target.getPosition();
&&int distanceToTarget = getPosition()
&&&&.getDistanceOfTarget(targetPosition);
&&setDistanceOfPrincess(distanceToTarget);
&private void setDistanceOfPrince(int distanceOfPrince)
&&this.distanceOfPrince = distanceOfP
&private int getDistanceOfPrincess()
&&return distanceOfP
&private void setDistanceOfPrincess(int distanceOfPrincess)
&&this.distanceOfPrincess = distanceOfP
&private void setFather(PositionWeight father)
&&this.father =
&private void setCost(int cost)
&&this.cost =
import java.util.ArrayL&
import java.util.L&
import javax.lang.model.element.UnknownElementE&
&* 迷宫地图
&* 类名称：Maze 类描述： 创建人：dobuy
public class MazeMap&
&&&& * 迷宫中的原点(0,0)
&&& private Position originP&
&&&& * 迷宫中的最大边界点
&&& private Position edgeP&
&&&& * 王子的位置
&&& private Position princeP&
&&&& * 公主的位置
&&& private Position princessP&
&&&& * 所有可达的位置集合（非墙壁）
&&& private List&Position& allReachableP&
&&& public MazeMap()&
&&&&&&& allReachablePositions = new ArrayList&Position&();&
&&&&&&& originPosition = new Position(0, 0);&
&&& public boolean isOverEdge(Position position)&
&&&&&&& if (getOriginPosition().getX() & position.getX()&
&&&&&&&&&&&&&&& || getOriginPosition().getY() & position.getY()&
&&&&&&&&&&&&&&& || getEdgePosition().getX() & position.getX()&
&&&&&&&&&&&&&&& || getEdgePosition().getY() & position.getY())&
&&&&&&& {&
&&&&&&&&&&&&
&&&&&&& }&
&&&& * 判断是否是墙
&&& public boolean isWall(Position currentPosition)&
&&&&&&& if (isOverEdge(currentPosition) || isPrincess(currentPosition)&
&&&&&&&&&&&&&&& || getPrincePosition().equals(currentPosition))&
&&&&&&& {&
&&&&&&&&&&&&
&&&&&&& }&
&&&&&&& return !getAllReachablePositions().contains(currentPosition);&
&&&& * 判断当前位置是否是公主位置
&&& public boolean isPrincess(Position currentPosition)&
&&&&&&& return getPrincessPosition().equals(currentPosition);&
&&&& * 初始化迷宫地址（坐标转换成点对象），并解析出王子的位置和公主的位置
&&&& * @param mazeMap 二维坐标表示的迷宫地图
&&& public void initMazeMap(char[][] mazeMap)&
&&&&&&& if (mazeMap == null || mazeMap.length &= 0)&
&&&&&&& {&
&&&&&&&&&&& throw new UnknownElementException(null, &null error&);&
&&&&&&& }&
&&&&&&& for (int column = 0; column & mazeMap[0]. column++)&
&&&&&&& {&
&&&&&&&&&&& for (int row = 0; row & mazeMap. row++)&
&&&&&&&&&&& {&
&&&&&&&&&&&&&&& parseMazePosition(new Position(row, column),&
&&&&&&&&&&&&&&&&&&&&&&& mazeMap[row][column]);&
&&&&&&&&&&& }&
&&&&&&& }&
&&&&&&& edgePosition = new Position(mazeMap.length, mazeMap[0].length);&
&&& public Position getPrincePosition()&
&&&&&&& return princeP&
&&& public Position getPrincessPosition()&
&&&&&&& return princessP&
&&&& * 解析迷宫的位置信息
&&& private void parseMazePosition(Position currentPosition, char thing)&
&&&&&&& switch (thing)&
&&&&&&& {&
&&&&&&& case '.':&
&&&&&&&&&&& getAllReachablePositions().add(currentPosition);&
&&&&&&&&&&&&
&&&&&&& case '*':&
&&&&&&&&&&&&
&&&&&&& case 'S':&
&&&&&&&&&&& setPrincePosition(currentPosition);&
&&&&&&&&&&&&
&&&&&&& case 'P':&
&&&&&&&&&&& setPrincessPosition(currentPosition);&
&&&&&&&&&&&&
&&&&&&& default:&
&&&&&&&&&&& throw new UnknownElementException(null, thing);&
&&&&&&& }&
&&& private Position getOriginPosition()&
&&&&&&& return originP&
&&& private Position getEdgePosition()&
&&&&&&& return edgeP&
&&& private void setPrincePosition(Position princePosition)&
&&&&&&& this.princePosition = princeP&
&&& private void setPrincessPosition(Position princessPosition)&
&&&&&&& this.princessPosition = princessP&
&&& private List&Position& getAllReachablePositions()&
&&&&&&& return allReachableP&
import java.util.ArrayL
import java.util.L
import javax.lang.model.element.UnknownElementE
&* 迷宫地图
&* 类名称：Maze 类描述： 创建人：dobuy
public class MazeMap
& * 迷宫中的原点(0,0)
&private Position originP
& * 迷宫中的最大边界点
&private Position edgeP
& * 王子的位置
&private Position princeP
& * 公主的位置
&private Position princessP
& * 所有可达的位置集合（非墙壁）
&private List&Position& allReachableP
&public MazeMap()
&&allReachablePositions = new ArrayList&Position&();
&&originPosition = new Position(0, 0);
&public boolean isOverEdge(Position position)
&&if (getOriginPosition().getX() & position.getX()
&&&&|| getOriginPosition().getY() & position.getY()
&&&&|| getEdgePosition().getX() & position.getX()
&&&&|| getEdgePosition().getY() & position.getY())
& * 判断是否是墙
&public boolean isWall(Position currentPosition)
&&if (isOverEdge(currentPosition) || isPrincess(currentPosition)
&&&&|| getPrincePosition().equals(currentPosition))
&&return !getAllReachablePositions().contains(currentPosition);
& * 判断当前位置是否是公主位置
&public boolean isPrincess(Position currentPosition)
&&return getPrincessPosition().equals(currentPosition);
& * 初始化迷宫地址（坐标转换成点对象），并解析出王子的位置和公主的位置
& * @param mazeMap 二维坐标表示的迷宫地图
&public void initMazeMap(char[][] mazeMap)
&&if (mazeMap == null || mazeMap.length &= 0)
&&&throw new UnknownElementException(null, &null error&);
&&for (int column = 0; column & mazeMap[0]. column++)
&&&for (int row = 0; row & mazeMap. row++)
&&&&parseMazePosition(new Position(row, column),
&&&&&&mazeMap[row][column]);
&&edgePosition = new Position(mazeMap.length, mazeMap[0].length);
&public Position getPrincePosition()
&&return princeP
&public Position getPrincessPosition()
&&return princessP
& * 解析迷宫的位置信息
&private void parseMazePosition(Position currentPosition, char thing)
&&switch (thing)
&&case '.':
&&&getAllReachablePositions().add(currentPosition);
&&case '*':
&&case 'S':
&&&setPrincePosition(currentPosition);
&&case 'P':
&&&setPrincessPosition(currentPosition);
&&default:
&&&throw new UnknownElementException(null, thing);
&private Position getOriginPosition()
&&return originP
&private Position getEdgePosition()
&&return edgeP
&private void setPrincePosition(Position princePosition)
&&this.princePosition = princeP
&private void setPrincessPosition(Position princessPosition)
&&this.princessPosition = princessP
&private List&Position& getAllReachablePositions()
&&return allReachableP
import javax.lang.model.element.UnknownElementE&
&* 迷宫类：包含王子和迷宫地图两个对象
public class Maze&
&&&& * 王子
&&& private P&
&&&& * 迷宫地图
&&& private MazeM&
&&& private boolean isInitOK =&
&&& public Maze(int time, char[][] map)&
&&&&&&& this.map = new MazeMap();&
&&&&&&& prince = new Prince(time);&
&&&&&&& initMap(map);&
&&& public void initMap(char[][] map)&
&&&&&&& try&
&&&&&&& {&
&&&&&&&&&&& getMap().initMazeMap(map);&
&&&&&&&&&&& getPrince().setMap(getMap());&
&&&&&&& }&
&&&&&&& catch (UnknownElementException e)&
&&&&&&& {&
&&&&&&&&&&& // TODO log&&
&&&&&&&&&&& isInitOK =&
&&&&&&& }&
&&&& * 游戏开始:返回结果：-1表示营救失败；0表示营救成功
&&& public int start()&
&&&&&&& if (!isInitOK)&
&&&&&&& {&
&&&&&&&&&&& return -1;&
&&&&&&& }&
&&&&&&& return getPrince().startToSearch();&
&&& private MazeMap getMap()&
&&& private Prince getPrince()&
import javax.lang.model.element.UnknownElementE
&* 迷宫类：包含王子和迷宫地图两个对象
public class Maze
&private P
& * 迷宫地图
&private MazeM
&private boolean isInitOK =
&public Maze(int time, char[][] map)
&&this.map = new MazeMap();
&&prince = new Prince(time);
&&initMap(map);
&public void initMap(char[][] map)
&&&getMap().initMazeMap(map);
&&&getPrince().setMap(getMap());
&&catch (UnknownElementException e)
&&&// TODO log
&&&isInitOK =
& * 游戏开始:返回结果：-1表示营救失败；0表示营救成功
&public int start()
&&if (!isInitOK)
&&&return -1;
&&return getPrince().startToSearch();
&private MazeMap getMap()
&private Prince getPrince()
import java.util.ArrayL&
import java.util.A&
import java.util.L&
&* 类名称：Prince 类描述： 创建人：dobuy
public class Prince&
&&&& * 营救公主失败
&&& private final static int FAIL = -1;&
&&&& * 营救公主成功
&&& private final static int SUCCESS = 0;&
&&&& * 剩余的时间
&&&& * 迷宫地图
&&& private MazeM&
&&&& * 正待尝试的位置集合(开启列表)
&&& private List&PositionWeight& attemptP&
&&&& * 已经经过的位置集合(关闭列表)
&&& private List&PositionWeight& passedP&
&&&& * 公主位置
&&& private PositionWeight princessP&
&&&& * 王子位置
&&& private PositionWeight princeP&
&&&& * 王子移动一步的所有偏移量
&&& private List&Position& offsets = Arrays.asList(new Position[] {&
&&&&&&&&&&& new Position(1, 0), new Position(0, 1), new Position(-1, 0),&
&&&&&&&&&&& new Position(0, -1) });&
&&& public Prince(int time)&
&&&&&&& this.time =&
&&&&&&& this.attemptPositions = new ArrayList&PositionWeight&();&
&&&&&&& this.passedPositions = new ArrayList&PositionWeight&();&
&&&& * 开始寻找公主
&&& public int startToSearch()&
&&&&&&& reset();&
&&&&&&& if (getPrincePosition().getPosition() == null&
&&&&&&&&&&&&&&& || getPrincessPosition().getPosition() == null || time & 0)&
&&&&&&& {&
&&&&&&&&&&& return FAIL;&
&&&&&&& }&
&&&&&&& // 1、添加王子自己的起始位置&&
&&&&&&& getAttemptPositions().add(getPrincePosition());&
&&&&&&& // 2、通过移动维护待尝试列表和已经尝试的列表&&
&&&&&&& attemptMove();&
&&&&&&& // 3、已经营救成功或者时间耗尽或者无法营救时，统计结果返回&&
&&&&&&& return getSpendTime();&
&&&& * 设置迷宫地图
&&& public void setMap(MazeMap map)&
&&&&&&& this.map =&
&&&& * 重置
&&& private void reset()&
&&&&&&& // 清空待尝试的列表&&
&&&&&&& getAttemptPositions().clear();&
&&&&&&& // 清空已经尝试的列表&&
&&&&&&& getPassedPositions().clear();&
&&&&&&& // 初始化王子的位置&&
&&&&&&& Position princePosition = getMap().getPrincePosition();&
&&&&&&& setPrincePosition(new PositionWeight(princePosition));&
&&&&&&& // 初始化公主的位置&&
&&&&&&& Position princessPosition = getMap().getPrincessPosition();&
&&&&&&& PositionWeight princessPositionWeight = new PositionWeight(&
&&&&&&&&&&&&&&& princessPosition);&
&&&&&&& setPrincessPosition(princessPositionWeight);&
&&&& * 可预知式移动
&&& private void attemptMove()&
&&&&&&& // 1、在如下2种情况下均结束：1)只要在待尝试列表中发现了公主，表明已经找到； 2)迷宫中所有可达的点都遍历完成，仍然无法找到&&
&&&&&&& if (getAttemptPositions().contains(getPrincessPosition())&
&&&&&&&&&&&&&&& || getAttemptPositions().isEmpty())&
&&&&&&& {&
&&&&&&&&&&&&
&&&&&&& }&
&&&&&&& // 2、获取最新加入的开销最小的节点&&
&&&&&&& PositionWeight minPositionWeight = getMinPositionWeight();&
&&&&&&& // 3、从待尝试列表中移除开销最小节点&&
&&&&&&& getAttemptPositions().remove(minPositionWeight);&
&&&&&&& // 4、把找到的开销最小节点加至已经尝试的列表&&
&&&&&&& getPassedPositions().add(minPositionWeight);&
&&&&&&& // 5、对当前的开销最小节点进行尝试，找出其所有子节点&&
&&&&&&& List&PositionWeight& subPositionWeights = getReachableSubPositions(minPositionWeight);&
&&&&&&& // 6、把所有子节点按照一定条件添加至待尝试列表&&
&&&&&&& for (PositionWeight subPositionWeight : subPositionWeights)&
&&&&&&& {&
&&&&&&&&&&& addPositionWeight(minPositionWeight, subPositionWeight);&
&&&&&&& }&
&&&&&&& // 7、重复以上操作&&
&&&&&&& attemptMove();&
&&&& * 王子从当前移动一步，可达的位置(忽略墙)
&&& private List&PositionWeight& getReachableSubPositions(PositionWeight father)&
&&&&&&& List&PositionWeight& subPositionWeights = new ArrayList&PositionWeight&();&
&&&&&&& Position fatherPosition = father.getPosition();&
&&&&&&& PositionWeight subPositionWeight =&
&&&&&&& Position subPosition =&
&&&&&&& for (Position offset : offsets)&
&&&&&&& {&
&&&&&&&&&&& subPosition = fatherPosition.offset(offset);&
&&&&&&&&&&& subPositionWeight = new PositionWeight(subPosition, father,&
&&&&&&&&&&&&&&&&&&& getPrincessPosition());&
&&&&&&&&&&& // 子节点越界或者是墙壁或者已经在尝试过的列表中时，不做任何处理&&
&&&&&&&&&&& if (getMap().isOverEdge(subPosition)&
&&&&&&&&&&&&&&&&&&& || getMap().isWall(subPosition)&
&&&&&&&&&&&&&&&&&&& || isInPassedTable(subPositionWeight))&
&&&&&&&&&&& {&
&&&&&&&&&&&&&&&&
&&&&&&&&&&& }&
&&&&&&&&&&& subPositionWeights.add(subPositionWeight);&
&&&&&&& }&
&&&&&&& return subPositionW&
&&&& * 添加一个点
&&& private void addPositionWeight(PositionWeight father,&
&&&&&&&&&&& PositionWeight positionWeight)&
&&&&&&& // 在待尝试列表中已经包含了当前点，则按照一定条件更新其父节点及其权值，否则直接添加&&
&&&&&&& if (getAttemptPositions().contains(positionWeight))&
&&&&&&& {&
&&&&&&&&&&& updateCostByFather(father, positionWeight);&
&&&&&&& }&
&&&&&&& else&
&&&&&&& {&
&&&&&&&&&&& getAttemptPositions().add(positionWeight);&
&&&&&&& }&
&&&& * 计算花费的时间
&&& private int getSpendTime()&
&&&&&&& if (getAttemptPositions().contains(getPrincessPosition()))&
&&&&&&& {&
&&&&&&&&&&& int princessIndex = getAttemptPositions().indexOf(&
&&&&&&&&&&&&&&&&&&& getPrincessPosition());&
&&&&&&&&&&& PositionWeight princess = getAttemptPositions().get(princessIndex);&
&&&&&&&&&&& return princess.getSpendTime() &= time ? SUCCESS : FAIL;&
&&&&&&& }&
&&&&&&& return FAIL;&
&&&& * 从待尝试列表中查找总开销值最小的点(如果有几个相同开销的最小点，取靠近队尾的)
&&& private PositionWeight getMinPositionWeight()&
&&&&&&& PositionWeight minPositionWeight = getAttemptPositions().get(0);&
&&&&&&& for (PositionWeight positionWeight : getAttemptPositions())&
&&&&&&& {&
&&&&&&&&&&& if (minPositionWeight.getCost() &= positionWeight.getCost())&
&&&&&&&&&&& {&
&&&&&&&&&&&&&&& minPositionWeight = positionW&
&&&&&&&&&&& }&
&&&&&&& }&
&&&&&&& return minPositionW&
&&&& * 如果从父节点移动至子节点的G值小于子节点之前的G值(前提是子节点已经在开启列表中)，则更新子节点的父节点及G值
&&& private void updateCostByFather(PositionWeight father,&
&&&&&&&&&&& PositionWeight subPosition)&
&&&&&&& int distanceOfAttemptFather = subPosition&
&&&&&&&&&&&&&&& .getDistanceFromAttemptFather(father);&
&&&&&&& int distanceOfPrince = father.getDistanceOfPrince()&
&&&&&&&&&&&&&&& + distanceOfAttemptF&
&&&&&&& if (distanceOfPrince & subPosition.getDistanceOfPrince())&
&&&&&&& {&
&&&&&&&&&&& subPosition.updateByFather(father);&
&&&&&&& }&
&&& private MazeMap getMap()&
&&& private boolean isInPassedTable(PositionWeight positionWeight)&
&&&&&&& return getPassedPositions().contains(positionWeight);&
&&& private List&PositionWeight& getAttemptPositions()&
&&&&&&& return attemptP&
&&& private List&PositionWeight& getPassedPositions()&
&&&&&&& return passedP&
&&& private PositionWeight getPrincessPosition()&
&&&&&&& return princessP&
&&& private void setPrincessPosition(PositionWeight princessPosition)&
&&&&&&& this.princessPosition = princessP&
&&& private PositionWeight getPrincePosition()&
&&&&&&& return princeP&
&&& private void setPrincePosition(PositionWeight princePosition)&
&&&&&&& this.princePosition = princeP&
import java.util.ArrayL
import java.util.A
import java.util.L
&* 类名称：Prince 类描述： 创建人：dobuy
public class Prince
& * 营救公主失败
&private final static int FAIL = -1;
& * 营救公主成功
&private final static int SUCCESS = 0;
& * 剩余的时间
& * 迷宫地图
&private MazeM
& * 正待尝试的位置集合(开启列表)
&private List&PositionWeight& attemptP
& * 已经经过的位置集合(关闭列表)
&private List&PositionWeight& passedP
& * 公主位置
&private PositionWeight princessP
& * 王子位置
&private PositionWeight princeP
& * 王子移动一步的所有偏移量
&private List&Position& offsets = Arrays.asList(new Position[] {
&&&new Position(1, 0), new Position(0, 1), new Position(-1, 0),
&&&new Position(0, -1) });
&public Prince(int time)
&&this.time =
&&this.attemptPositions = new ArrayList&PositionWeight&();
&&this.passedPositions = new ArrayList&PositionWeight&();
& * 开始寻找公主
&public int startToSearch()
&&reset();
&&if (getPrincePosition().getPosition() == null
&&&&|| getPrincessPosition().getPosition() == null || time & 0)
&&&return FAIL;
&&// 1、添加王子自己的起始位置
&&getAttemptPositions().add(getPrincePosition());
&&// 2、通过移动维护待尝试列表和已经尝试的列表
&&attemptMove();
&&// 3、已经营救成功或者时间耗尽或者无法营救时，统计结果返回
&&return getSpendTime();
& * 设置迷宫地图
&public void setMap(MazeMap map)
&&this.map =
&private void reset()
&&// 清空待尝试的列表
&&getAttemptPositions().clear();
&&// 清空已经尝试的列表
&&getPassedPositions().clear();
&&// 初始化王子的位置
&&Position princePosition = getMap().getPrincePosition();
&&setPrincePosition(new PositionWeight(princePosition));
&&// 初始化公主的位置
&&Position princessPosition = getMap().getPrincessPosition();
&&PositionWeight princessPositionWeight = new PositionWeight(
&&&&princessPosition);
&&setPrincessPosition(princessPositionWeight);
& * 可预知式移动
&private void attemptMove()
&&// 1、在如下2种情况下均结束：1)只要在待尝试列表中发现了公主，表明已经找到； 2)迷宫中所有可达的点都遍历完成，仍然无法找到
&&if (getAttemptPositions().contains(getPrincessPosition())
&&&&|| getAttemptPositions().isEmpty())
&&// 2、获取最新加入的开销最小的节点
&&PositionWeight minPositionWeight = getMinPositionWeight();
&&// 3、从待尝试列表中移除开销最小节点
&&getAttemptPositions().remove(minPositionWeight);
&&// 4、把找到的开销最小节点加至已经尝试的列表
&&getPassedPositions().add(minPositionWeight);
&&// 5、对当前的开销最小节点进行尝试，找出其所有子节点
&&List&PositionWeight& subPositionWeights = getReachableSubPositions(minPositionWeight);
&&// 6、把所有子节点按照一定条件添加至待尝试列表
&&for (PositionWeight subPositionWeight : subPositionWeights)
&&&addPositionWeight(minPositionWeight, subPositionWeight);
&&// 7、重复以上操作
&&attemptMove();
& * 王子从当前移动一步，可达的位置(忽略墙)
&private List&PositionWeight& getReachableSubPositions(PositionWeight father)
&&List&PositionWeight& subPositionWeights = new ArrayList&PositionWeight&();
&&Position fatherPosition = father.getPosition();
&&PositionWeight subPositionWeight =
&&Position subPosition =
&&for (Position offset : offsets)
&&&subPosition = fatherPosition.offset(offset);
&&&subPositionWeight = new PositionWeight(subPosition, father,
&&&&&getPrincessPosition());
&&&// 子节点越界或者是墙壁或者已经在尝试过的列表中时，不做任何处理
&&&if (getMap().isOverEdge(subPosition)
&&&&&|| getMap().isWall(subPosition)
&&&&&|| isInPassedTable(subPositionWeight))
&&&subPositionWeights.add(subPositionWeight);
&&return subPositionW
& * 添加一个点
&private void addPositionWeight(PositionWeight father,
&&&PositionWeight positionWeight)
&&// 在待尝试列表中已经包含了当前点，则按照一定条件更新其父节点及其权值，否则直接添加
&&if (getAttemptPositions().contains(positionWeight))
&&&updateCostByFather(father, positionWeight);
&&&getAttemptPositions().add(positionWeight);
& * 计算花费的时间
&private int getSpendTime()
&&if (getAttemptPositions().contains(getPrincessPosition()))
&&&int princessIndex = getAttemptPositions().indexOf(
&&&&&getPrincessPosition());
&&&PositionWeight princess = getAttemptPositions().get(princessIndex);
&&&return princess.getSpendTime() &= time ? SUCCESS : FAIL;
&&return FAIL;
& * 从待尝试列表中查找总开销值最小的点(如果有几个相同开销的最小点，取靠近队尾的)
&private PositionWeight getMinPositionWeight()
&&PositionWeight minPositionWeight = getAttemptPositions().get(0);
&&for (PositionWeight positionWeight : getAttemptPositions())
&&&if (minPositionWeight.getCost() &= positionWeight.getCost())
&&&&minPositionWeight = positionW
&&return minPositionW
& * 如果从父节点移动至子节点的G值小于子节点之前的G值(前提是子节点已经在开启列表中)，则更新子节点的父节点及G值
&private void updateCostByFather(PositionWeight father,
&&&PositionWeight subPosition)
&&int distanceOfAttemptFather = subPosition
&&&&.getDistanceFromAttemptFather(father);
&&int distanceOfPrince = father.getDistanceOfPrince()
&&&&+ distanceOfAttemptF
&&if (distanceOfPrince & subPosition.getDistanceOfPrince())
&&&subPosition.updateByFather(father);
&private MazeMap getMap()
&private boolean isInPassedTable(PositionWeight positionWeight)
&&return getPassedPositions().contains(positionWeight);
&private List&PositionWeight& getAttemptPositions()
&&return attemptP
&private List&PositionWeight& getPassedPositions()
&&return passedP
&private PositionWeight getPrincessPosition()
&&return princessP
&private void setPrincessPosition(PositionWeight princessPosition)
&&this.princessPosition = princessP
&private PositionWeight getPrincePosition()
&&return princeP
&private void setPrincePosition(PositionWeight princePosition)
&&this.princePosition = princeP
单元测试类：
import static org.junit.Assert.assertE&
import org.junit.T&
&* 类名称：MazeTest 类描述： 创建人：dobuy
public class MazeTest&
&&& private M&
&&& private char[][]&
&&&& * 营救公主失败
&&& private final static int FAIL = -1;&
&&&& * 营救公主成功
&&& private final static int SUCCESS = 0;&
&&&& * testStart01 正常可达情况
&&& @Test&
&&& public void testStart01()&
&&&&&&& map = new char[][] { { '.', '.', '.', '.' }, { '.', '.', '.', '.' },&
&&&&&&&&&&&&&&& { '.', '.', '.', '.' }, { 'S', '*', '*', 'P' } };&
&&&&&&& maze = new Maze(5, map);&
&&&&&&& assertEquals(maze.start(), SUCCESS);&
&&&& * testStart02 正常不可达情况
&&& @Test&
&&& public void testStart02()&
&&&&&&& map = new char[][] { { '.', '.', '.', '.' }, { '.', '.', '.', '.' },&
&&&&&&&&&&&&&&& { '.', '.', '.', '.' }, { 'S', '*', '*', 'P' } };&
&&&&&&& maze = new Maze(2, map);&
&&&&&&& assertEquals(maze.start(), FAIL);&
&&&& * testStart03 参数异常
&&& @Test&
&&& public void testStart03()&
&&&&&&& map =&
&&&&&&& maze = new Maze(2, map);&
&&&&&&& assertEquals(maze.start(), FAIL);&
&&&&&&& map = new char[][] {};&
&&&&&&& maze = new Maze(2, map);&
&&&&&&& assertEquals(maze.start(), FAIL);&
&&&&&&& map = new char[][] { { '.', '.', '.', '.' }, { '.', '.', '.', '.' },&
&&&&&&&&&&&&&&& { '.', '.', '.', '.' }, { '.', '.', '.', '.' } };&
&&&&&&& maze = new Maze(2, map);&
&&&&&&& assertEquals(maze.start(), FAIL);&
&&&&&&& map = new char[][] { { '.', '.', '.', '.' }, { '.', '.', '.', '.' },&
&&&&&&&&&&&&&&& { 'S', '.', '.', 'P' }, { '.', '.', '.', '.' } };&
&&&&&&& maze = new Maze(-1, map);&
&&&&&&& assertEquals(maze.start(), FAIL);&
&&&& * testStart04 临界值
&&& @Test&
&&& public void testStart04()&
&&&&&&& map = new char[][] { { '*', '*', '*', '*' }, { '*', '*', '*', '*' },&
&&&&&&&&&&&&&&& { '*', '*', '*', '.' }, { 'S', '*', '*', 'P' } };&
&&&&&&& maze = new Maze(2, map);&
&&&&&&& assertEquals(maze.start(), FAIL);&
&&&&&&& map = new char[][] { { '.', '.', '.', '.' }, { '.', '.', '.', '.' },&
&&&&&&&&&&&&&&& { 'S', 'P', '.', '*' }, { '.', '.', '.', '.' } };&
&&&&&&& maze = new Maze(1, map);&
&&&&&&& assertEquals(maze.start(), SUCCESS);&
(window.slotbydup=window.slotbydup || []).push({
id: '2467140',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467141',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467143',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467148',
container: s,
size: '1000,90',
display: 'inlay-fix'}