问答题

[说明]
一个印刷电路板的布线区域可分成n*m个方格，如图3-1(a)所示，现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布线，如图3-1（b）中虚线所示。为了避免线路相交，应将已布过线的方格作封锁标记，其他线路不允许穿过被封锁的方格。

设给定印刷电路板的起始方格x与目的方格y尚未布线，求这两个方格间最短布线方案的基本思路是：从起始方格x开始，先考查距离起始方格距离为1的可达方格并用一个路径长度值标记，然后依次考查距离为2、3、…的可达方格，直到距离为k的某一个可达方格就是目标方格y时为止，或者由于不存在从x到y的布线方案而终止。布线区域中的每一个方格与其相邻的上、下、左、右四个方格之间的距离为1，依次沿下、右、上、左这四个方向考查，并用一个队列记录可达方格的位置。表3-1给出了沿这四个方向前进1步时相对于当前方格的相对偏移量。

例如，设印刷板的布线区域可划分为一个6*8的方格阵列，如图3-2(a)所示，其中阴影表示已封锁方格。从起始方格x（位置[3，2]，标记为0）出发，按照下、右、上、左的方向依次考查，所标记的可达方格如图3-2（a）所示，目标方格为y（位置[4，7]，标记为10），相应的最短布线路径如图3-2（b）虚线所示。





● 供选择的答案
[a] Found ≠true 　[b] Found =true
[c] T = Endpos　 　[d] Q.insert(T)
[e] T←Q.delete()　[f] CurPos = EndPos
[g] I ≥ 4 [h] Curpos←Q.delete()
[I] Grid [T.row,T.col] = -1[j] Grid [T.row , T.col] ≠ -1