布线问题的解决方案：主要是采用队列式分支限界法。布线问题的解空间是一个图。解此
问题的队列式分支限界法从起始位置 a 开始将它作为第一个扩展节点。与该扩展节点相邻
并且可达的方格成为可行节点被加入到活节点队列中，并且将这些方格标记为 1，即从起
始方格 a 到这些方格的距离为 1.接着，算法从活节点队列中却出队首节点作为下一个扩展
节点，并将于当前扩展节点相邻并且未标记过的方格标记为 2，并存入活节点队列。这个
过程一直继续到算法搜索到目标方格 b 或活节点队列为空为止。
在实现上述算法时，首先定义一个表示电路板上方格位置的类 Position，他的两个私有成员
row 和 col 分别表示方格所在的行和列。在电路帮的任何一个方格处，布线可沿着右、下、
左 、 上 四 个 方 向 进 行 。 沿 这 4 个 方 向 的 移 动 丰 碑 为 移 动 0 ， 1 ， 2 ， 3. 在 表 6-1 中 ，
offset[i].row 和 offset[i].col（i=0,1,2,3）分别给出沿这四个方向前进一步相对于当前方格的
相对位移.
表 6-1 移动方向的相对位移
移动 i 方向
offset[i].row offset[i].col
0
1
2
3
右
下
左
上
0 1
1 0
0 -1
-1 0
在实现上述算法时，用二维数组 grid 表示所给的方格阵列。初始时，grid[i][j]=0,鄙视该
方格允许布线；而 grid[i][j]=1 表示方格被封锁，不允许布线。为了便于处理方格边界的情
况，算法在所给方格阵列四周设置一道“围墙”，即增设标记为“ 1”的附加方格。算法开始时
测试初始方格与目标方格是否相同。如果这两个方格相同则不必计算，直接返回最短距离
0，否则算法设置方格阵列的“围墙”，初始化位移矩阵 offset。算法将其实位置的距离标记
为 2.由于数字 0 和 1 表示方格的开放或封锁状态，所以在表示距离时不用这两个数字，因
而将距离的值都加 2。实际距离应为标记距离减去 2.算法从起始位置 start 开始，标记所有
标记距离为 3 的方格并存入活节点队列，然后依次标记所有标记距离为 4，5，…的方格，
直至到达目标方格 finish 或活节点队列为空时为止。
