问答题 [说明]
一个印制电路板的布线区域可分成n×m个方格，如图1(a)所示，现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布线，如图1(b)中虚线所示。为了避免线路相交，应将已布过线的方格作成封锁标记，其他线路不允许穿过被封锁的方格。
设给定印制电路板的起始方格x与目的方格y尚未布线，求这两个方格间最短布线方案的基本思路是：从起始方格x开始，先考查距离起始方格距离为k的某一个可达方格就是目标方格y时为止，或者由于不存在从x到y的布线方案而终止。布线区域中的每一个方格与其相邻的上、下、左、右4个方格之间的距离为1，依次沿下、右、上、左这4个方向考查，并用一个队列记录可达方格的位置。下表给出了沿这4个方向前进1步时相对于当前方格的相对偏移量。

沿4个方向前进1步时相对于当前方格的相对偏移量
搜索顺序i	方向	行偏移量	列偏移量
0	上	-1	0
1	右	0	1
2	上	-1	0
3	左	0	-1

例如，设印制电路板的布线区域可划分为一个6×8的方格阵列，如图2(a)所示，其中阴影表示已封锁方格。从起始方格x(位置[3，2]，标记为0)出发，按照下、右、上、左的方向依次考查，所标记的可达方格如图2(a)所示，目标方格为y(位置[4，7]，标记为10)，相应的最短布线路径如图2(b)中虚线所示。 图3和图4所示的流程图即利用上述思路在电路板方格阵列中进行标记，图中使用的主要符号如下表所示。在图3中，设置电路板初始格局，即将可布线方格置为数值-1、已布线方格(即封锁方格)置为-9。设置方格阵列“围墙”的目的是省略方格位置的边界条件判定，方法是在四周附加格，并将其标记为-9(与封锁标记相同)。