编程介的小学生 2019-09-14 21:36 采纳率: 20.5%
浏览 225

Traffic Jam 交通问题怎么实现

Description

Traffic jam is a real nightmare of all drivers. Nobody likes to be stuck in the overfilled streets, when the cars move very slowly, or they even don't move at all. Professional drivers face traffic jams quite often. Truck drivers of ACM are not an exception. Can you help drivers to find the way out of the traffic jam?

We can model a small (but complicated) traffic jam on a 6*6 grid of squares. Vehicles (cars and trucks) are scattered over the grid at integer locations, as shown below. Both types of vehicles are 1 square wide. Cars are 2 squares long, and trucks are 3 squares long. Vehicles may be oriented either horizontally (East-West) or vertically (North-South) relative to the grid.

Vehicles cannot move through each other, cannot turn, and cannot move over the edge of the grid. They can move in their direction (horizontally-oriented vehicles cannot move vertically and vice versa), as long as they are not blocked by another vehicle or by the edge of the grid. Only one vehicle may move in a single step, but it may move by as many squares at a time as possible, providing there is enough empty space.

Our goal is to move vehicles back and forth until a particular horizontally-oriented vehicle (your own car -- the black one on the picture above) leaves the rightmost (eastern-most) edge of the grid, where it is considered to have escaped the traffic jam. You are to write a program that will find a solution requiring the minimum possible number of moves.
Input

The input file will consist of one or more input scenarios. Each scenario begins with a single integer n, 1 <= n <= 10, giving the number of vehicles in the scenario. Then there will be 6 lines of input, each containing 6 characters. Each character is either a dot (".") representing an empty square, or a lowercase letter representing a vehicle. Your own vehicle is always oriented horizontally and represented by "x" characters. The other vehicles use the letters sequentially, beginning with "a".

The last scenario will be followed by a line containing a single zero.
Output

For each scenario, output a single line with the statement "Scenario #K requires X moves.", where K is the number of the scenario (starting with 1) and X is the minimum number of moves required to escape the traffic jam with the particular car.

If it is not possible to escape, output the sentence "You are trapped in scenario #K." instead.
Sample Input

8
aa...b
c..d.b
cxxd.b
c..d..
e...ff
e.ggg.
8
abbc..
a..c..
axxc..
..gddd
..g..e
..fffe
0
Sample Output

Scenario #1 requires 8 moves.
Scenario #2 requires 25 moves.

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 MATLAB怎么通过柱坐标变换画开口是圆形的旋转抛物面?
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题
    • ¥15 Visual Studio问题
    • ¥20 求一个html代码,有偿