UVa 10047：The Monocycle， 优先队列+BFS2014-10-11 csdn博客 shuangde800题目链接：http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=988题目类型：搜索，优先队列题目：A monocycle is a cycle that runs on one wheel and the one we will be considering is a bit more special. It has a solid wheel colored with five different colors as shown in the figure:
The colored segments make equal angles （72o） at the center. A monocyclist rides this cycle on an
grid of square tiles. The tiles have such size that moving forward from the center of one tile to that of the next one makes the wheel rotate exactly 72o around its own center. The effect is shown in the above figure. When the wheel is at the center of square 1, the midpoint of the periphery of its blue segment is in touch with the ground. But when the wheel moves forward to the center of the next square （square 2） the midpoint of its white segment touches the ground.
Some of the squares of the grid are blocked and hence the cyclist cannot move to them. The cyclist starts from some square and tries to move to a target square in minimum amount of time. From any square either he moves forward to the next square or he remains in the same square but turns 90o left or right. Each of these actions requires exactly 1 second to execute. He always starts his ride facing north and with the midpoint of the green segment of his wheel touching the ground. In the target square, too, the green segment must be touching the ground but he does not care about the direction he will be facing.Before he starts his ride, please help him find out whether the destination is reachable and if so the minimum amount of time he will require to reach it.题目大意翻译：有一个独轮车，轮子上有5个不同的扇形颜色区域， 每个区域大小都是相等的（72°扇形）。 骑着这个车子在一个广场上行走。广场是有大小相同的正方形瓷砖铺成的。 独轮车从一块瓷砖走向相邻的一块，轮子正好转72°。只能走向相邻的上、下、左、右的瓷砖。从一个瓷砖走向下一个瓷砖耗费1秒钟。车子转方向90°耗费1秒钟，连转180°就要费2秒钟。白色的瓷砖可以走，黑色的不可以走（黑色的用"#"代替，白色的用"."代替）。题目要求从标有S的地方走向标有T的地方。轮子在开始时，蓝色是贴着地面的，要求到达终点时，也正好是蓝色贴着地面的。如果可以到达的话，输出所需要的最短时间。否则输出 destination not reachable。URL：http://www.bianceng.cn/Programming/sjjg/201410/45714.htm
易网时代-编程资源站