程序设计实习：12.2小游戏|163

小游戏问题描述

一天早上, 你起床的时候想 “我编程序这么牛 , 为什么不能靠这个赚点小钱呢?” 因此你决定编写一个小游戏

游戏在一个分割成 w * h 个正方格子的矩形板上进行

每个正方格子上可以有一张游戏卡片, 当然也可以没有

小游戏问题描述

当下面的情况满足时, 认为两个游戏卡片之间有一条路径相连:

路径只包含水平或者竖直的直线段

路径不能穿过别的游戏卡片

但是允许路径临时的离开矩形板

这是一个例子:

在 (1,3)和 (4,4)处的游戏卡片是可以相连的而在 (2,3) 和 (3,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.”

每组数据之后输出一个空行

问题分析 (1) 迷宫求解问题自相似性表现在每走一步的探测方式相同, 可以用递归方法求解通过枚举方式找到从起点到终点的路径, 朝一个方向走下去:

如果走不通, 则换个方向走四个方向都走不通, 则回到上一步的地方, 换个方向走依次走下去, 直到走到终点 9 问题分析 (1) 计算路径数目: 普通迷宫问题的路径数目是经过的格子数目而该问题路径只包含水平或者竖直的直线段, 所以需要记录每一步走的方向

如果上一步走的方向和这一步走的方向相同, 递归搜索时路径数不变, 否则路径数加1

路径只包含水平或者竖直的直线段. 路径不能穿过别的游戏卡片. 但是允许路径临时的离开矩形板所以在矩形板最外层增加一圈格子, 路径可以通过这些新增加的格子 11 问题分析 (3) 描述迷宫: 1. 设置迷宫为二维数组board[][], 数组的值是: 空格: 代表这个地方没有游戏卡片 ‘X’ : 代表这个地方有游戏卡片 2. 在搜索过程中, 用另外一个二维数mark[][]标记格子是否已经走过了 mark[i][j]=0 //格子(i, j)未走过 mark[i][j]=1 //格子(i, j)已经走过 3. int minstep, w, h; //全局变量 //minstep, 记录从起点到达终点最少路径数, //初始化为一个很大的数 //w, h矩形板的宽度和高度

判断新位置(x, y)是否有效

T1: (x, y)在边界之内 (x > -1) && (x < w + 2) && (y > -1) && (y < h + 2)

T2: 该位置没有游戏卡片并且未曾走过 ((board[y][x] == ' ') && (mark[y][x] == false))

T3: 已经到达终点 (x == end_x) && (y == end_y) && (board[y][x] == 'X‘) 综上, (x,y)有效的条件是 T1 && (T2 || T3) ((x > -1) && (x < w + 2) && (y > -1) && (y < h + 2) && (((board[y][x] == ' ') && (mark[y][x] == false)) || ((x == end_x) && (y == end_y) && (board[y][x] == 'X')))) 14 递归方法构造递归函数