W12-02_递归-小游戏.pdf

1 递归— 小游戏 郭 炜 刘家瑛 北京大学 程序设计实习 小游戏 问题描述 • 一天早上, 你起床的时候想 “我编程 序这么牛, 为什么不能靠这个赚点小钱呢?” 因此你决定编写一个小游戏 • 游戏在一个分割成 w * h 个正方格 子的矩形板上进行 • 每个正方格子上可以有一张游戏卡 片, 当然也可以没有 2 小游戏 问题描述 • 当下面的情况满足时, 认为两个游戏卡片之间有一条路径相连: • 路径只包含水平或者竖直的直线段 • 路径不能穿过别的游戏卡片 • 但是允许路径临时的离开矩形板 3 这是一个例子: (1,3) (2,3) (5,3) (3,4) (4,4) 在 (1,3)和 (4,4)处的游戏卡片是可以相连的 而在 (2,3) 和 (3,4) 处的游戏卡是不相连的, 因为连接它们 的每条路径都必须要穿过别的游戏卡片 现在要在小游戏里面判断: 是否存在一条满足题意的路径能连接给定的两个游戏卡片 4 输入 (1/2) • 输入包括多组数据: 一个矩形板对应一组数据 • 第一行包括两个整数 w和h (1 = w, h = 75), 分别表示矩形板的宽度和长度 • 下面的h行, 每行包括w个字符, 表示矩形板上的游戏卡 片分布情况: • 使用 ‘X’ 表示这个地方有一个游戏卡片 • 使用 空格 表示这个地方没有游戏卡片 5 输入 (2/2) • 之后每行上包括4个整数: x1, y1, x2, y2 (1 = x1, x2 = w, 1 = y1, y2 = h) • 给出两个卡片在矩形板上的位置 注意: 矩形板左上角的坐标是(1,1) 输入保证这两个游戏卡片所处的位置是不相同的 如果一行上有4个0, 表示这组测试数据的结束 • 如果一行上给出w = h = 0, 那么表示所有的输入结束了 6 输出 • 对每一个矩形板, 输出一行 “Board #n:”, n是输入数据的 编号 • 对每一组需要测试的游戏卡片输出一行. 这一行的开头 是 “Pair m: ”, 这里m是测试卡片的编号（对每个矩形板, 编号都从1开始） • 如果可以相连, 找到连接这两个卡片的所有路径中包括 线段数最少的路径, 输出 “k segments.” k是找到的最优路径中包括的线段的数目 • 如果不能相连, 输出 “impossible.” • 每组数据之后输出一个空行 7 样例输入 样例输出 5 4 Board #1: X X X X X X X Pair 1: 4 segments. X X X X Pair 2: 3 segments. X X X Pair 3