1、问题描述
开关盒布线问题是这样的：给定一个矩形布线区域，其外围有若干针脚。两个针脚之间通过布设一条金属线路而实现互连。这条线路被称为电线，被限制在矩形区域内。如果两条电线发生交叉，则会发生电流短路。所以，不允许电线间的交叉。每对互连的针脚被称为网组。我们的目标是要确定对于给定的网组，能否合理地布设电线以使其不发生交叉。图 5-7a 给出了一个布线的例子，其中有八个针脚和四个网组。四个网组分别是 ( 1 , 4 , )， ( 2 , 3 )， ( 5 , 6 )和( 7 , 8 )。图5 -7b 给出的布线方案有交叉现象发生（ (1,4) 和(2,3) 之间），而图 5-7c 则没有交叉现象发生。由于四个网组可以通过合理安排而不发生交叉， 因此可称其为可布线开关盒（ routable switch box）。我们要解决的问题是，给定一个开关盒布线实例，确定它是不是一个可布线的。
2、解决思路
为了解决开关盒布线问题，我们注意到，当两个针脚互连时，其电线把布线区分成两个分区。例如，当 ( 1 , 4 )互连时，就得到了两个分区，一个分区包含针脚 2和3，另一个分区包含针脚5 ~ 8。现在如果有一个网组，其两个针脚分别位于这两个不同的分区，那么这个网组是不可以布线的，因而整个电路也是不可布线的。如果没有这样的网组，则可以继续判断每个独立的分区是不是可布线的。为此，可以从一个分区中取出一个网组，利用该网组把这个分区又分成两个子分区，如果任一个网组的两个针脚都分布在同一个子分区之中（即不会出现两个针脚分别位于两个子分区的情形），那么这个分区就是可布线的。
为了实现上述策略，可以按顺时针或反时针方向沿着开关盒的外围进行遍历，可从任意一个针脚开始。例如，如果按顺时针方向从针脚 1 开始遍历图 5-7a 中的针脚，那么将依次检查针脚1, 2, ..., 8。针脚1 和4属于同一个网组，那么在针脚 1至针脚4之间出现的所有针脚构成了第一个分区，而在针脚 4至针脚 1 之间出现的所有针脚构成了第二个分区。把针脚 1 放入堆栈，然后继续处理，直至遇到针脚 4。这个过程使我们仅在处理完一个分区之后才能进入下一个分区。下一个针脚是针脚 2，它与针脚 3同属一个网组，它们又把当前分区分成两个子分区。与前面的做法一样，把针脚2放入堆栈，然后继续处理直至遇到针脚3。由于针脚3与针脚2属同一个网组，而针脚2正处在栈顶，这表明已经处理完一个子分区，因此可将针脚 2从栈顶删除。接下来将到针脚4，由于与之互连的针脚 1正处在栈顶，因此当前的分区已经处理完毕，可从栈顶删除针脚1 。按照这种方法继续进行下去，直至检查完八个针脚，堆栈变空，所创建的分区都已处理完毕为止。
而对于不可布线的开关盒，最后堆栈不会为空。
3、代码实现
堆栈的实现见：堆栈的链表方式实现
1 #include "Checkbox.h" 2 //net存储开关盒针脚的分组编号，n为针脚个数 3 bool CheckBox(int net[],int n) 4 { 5 LinkedStack<int> S; 6 if (n<=0) 7 { 8 throw OutofBounds(); 9 } 10 11 for (int i = 0; i < n;++i) 12 { 13 if (S.IsEmpty()) 14 { 15 S.Add(net[i]);//堆栈为空，直接添加 16 continue; 17 } 18 19 if (S.Top()==net[i])//等于栈顶，说明可以直接走线 20 { 21 int temp; 22 S.Delete(temp); 23 } 24 else 25 { 26 S.Add(net[i]); 27 } 28 } 29 30 return S.IsEmpty();//堆栈空说明无交叉可布线 31 }
1 #include "Checkbox.h" 2 #include <istream> 3 4 int main() 5 { 6 int net[] = { 1, 2, 3, 2, 1, 3, 4, 4 }; 7 8 if (CheckBox(net, 8)) 9 { 10 std::cout << "可布线开关盒" << std::endl; 11 } 12 else 13 { 14 std::cout << "不可布线开关盒" << std::endl; 15 } 16 17 system("pause"); 18 19 return 0; 20 }
输出:
