文档介绍：第4章程序流程图
【典型题11
阅读以下说明和流程图，从供选择的答案中选出应填入流程图处的字句写在对应栏内。
【说明】
一个印刷电路板的布线区域可分成nXm个方格，如图4-l(a)所示，现在需要确定电路板中给定的两 个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布线，如图4-1 (b)中虚线所示。为了避 免线路相交，应将已布过线的方格做成封锁标记，其他线路不允许穿过被封锁的方格。
(・)布紈区域方格阵死
1
1
1
1
(b)水平或垂直布找
图4U典型题1
设给定印刷电路板的起始方格X与目的方格y尚未布线，求这两个方格间最短布线方案的基本思路是: 从起始方格x开始，考查与起始方格距离为k的某一个可达方格是目标方格y时为止，或者由于不存在从 x到y的布线方案而终止。布线区域中的每一个方格与其相邻的上、下、左、右4个方格之间的距离为1, 依次沿下、右、上、左这4个方向考查，并用一个队列记录可达方格的位置。表4-1给出了沿这4个方向 前进1步时相对于当前方格的相对偏移量。
表4-1相对彳
扁移量
搜索顺序i
方向
行偏移量
列偏移量
0
上
-1
0
1
右
0
1
2
上
-1
0
3
左
0
-1
例如，设印刷电路板的布线区域可划分为一个6X8的方格阵列，如图4-2(a)所不，其中阴影表不已封 锁方格。从起始方格x(位置[3, 2],标记为0)出发，按照下、右、上、左的方向依次考查，所标记的可达
(»标记盹离
布越殆径
图4-2布线实例
如图4-3和图4-4所不的流程图即利用上述思路，在电路板方格阵列中进彳丁标记，图中使用的主要符 号如表4-2所示。在图4-4中，设置电路板初始格局，即将可布线方格置为数值-1、已布线方格(即封锁方 格)置为-9。设置方格阵列“围墙”的目的是省略方格位置的边界条件判定，方法是在四周附加格，并将其 标记为-9(与封锁标记相同)。
表4-2主要符号
符号
含义
Grid
全局二维数组Grid[N+2, M+2],表示电路板方格阵列，初始时数组元素Grid：!, j]的值为-1表示当 前方格可布线，为-9表示前方格不可布线
offset
一维数组offset [4] : offset [i] （OWIW3）的分量为r （行偏移景）和c （列偏移量）,按照表4-1的内容 设置其值
Startpos>
Endpos>
Cuapos> T
分别表示起始方格、目标方格、当前方格和临吋方格，其位置用分量度row和col确定
Q. insen(s)
将方格s的位置信息加入队列
Q. delete ()
删除非空队列的队头元素，并返回该元素
Q. emplyO
若队列Q为空，则返回true；否则返回false
图4-3对电路板进行标记（一）
图4, 对电路板进行标记(二)
供选择的答案：
[a]Found^true [b]Found=true
[c]T=EndPos [d](T)
[e] T—Q. delete() [f] CurPos=EndPos