软考软件设计师资料
09年5月软设第5部分工作流程和算法流程
第5部分流程类(工作流程和算法流程) ●试题1
阅读以下说明和流程图，从供选择的答案中选出应填人流程图(n)处的字句写在答题纸的对应栏内。
【说明】
某游戏的地图区域可分成n×m个方格，如图5．1(a)所示，现在需要确定区域中给定的两个方格的中心点之间的最短前进方案。前进路线只能沿水平或垂直方向，如图5．1(b)中虚线所示。为了避免路线相交，应将有障碍的方格作封锁标记，其他线路不允许穿过被封锁的方格。
设给定地图区域的起始方格a与目的方格b尚未被封锁，求这两个方格问最短前进方案的基本思路是：从起始方格a开始，先考查距离起始方格距离为1的可达方格并用一个路径长度值标记，然后依次考查距离为2、3、 的可达方格，直到距离为k的某一个可达方格就是目标方格b时为止，或者由于不存在从a到b的前进方案而终止。地图区域中的每一个方格与其相邻的上、下、左、右四个方格之间的距离为1，依次沿下、右、上、左这四个方向考查，并用一个队列记录可达方格的位置。表5．1给出了沿这四个方向前进l步时相对于当前方格的相对偏移量。
表5．1
FROM：及时雨
软考软件设计师资料
例如，设游戏的地图区域可划分为一个6×8的方格阵列，如图5．2(a)所示，其中阴影表示已封锁方格。从起始方格a(位置[3，2]，标记为0)出发，按照下、右、上、左的方向依次考查，所标记的可达方格如图5．2(a)所示，目标方格为b(位置[4，7]，标记为10)，相应的最短前进路径如图5．2(b)虚线所示如图5．3和图5．4所示的流程图即利用了上述思路，在地图方格阵列中进行标记，图中使用的主要符号见表5．2。在图5．4中，设置地图初始格局，即将可前进方格置为数值－1、已前进方格(即封锁方格)置为－9。设置方格阵列“围墙”的目的是省略方格位置的边界条件判定，方法是在四周附加方格，并将其标记为－9(与封锁标记相同)。
FROM：及时雨