《数据结构、算法与应用C++语言描述》-栈的应用-开关盒布线问题

开关盒布线问题

问题描述

在开关盒布线问题中，给定一个矩形布线区域，其外围有若干管脚。两个管脚之间通过布设一条金属线路来连接。这条金属线路称为电线，它被限制在矩形区域内。两条电线交叉会发生电流短路。因此，电线不许交叉。每对要连接的管脚称为一个网组。对于给定的一些网组，我们需要确定，它们能否连接而又不发生交叉。图 8-8a是一个布线的示例，其中有8个管脚和4个网组。四个网组分别是（1，4），（2，3），（5，6）和（7，8）。图8-8b的布线在网组（1，4）和（2，3）之间有交叉，而图 8-8c的布线没有交叉。因为这 4 个网组的布线可以没有交叉，所以这个开关盒称为可布线开关盒（routable switch box）。（在现实问题中，两个相邻的电线之间还要求保留一个最小的间隙，但是我们忽略这个额外的要求。）我们的问题是，输入一个开关盒布线实例，然后确定它是否可以布线。图8-8b和图8-8c的电线都是与x轴和y轴平行的直线段，但与轴不平行的直线段或曲线段也是可以的。

求解策略

为了解决开关盒布线问题，我们注意到，当一个网组互连时，连线把布线区域分隔成两个分区。分区边界上的管脚属于哪一个分区与连线无关，而与互连网组的管脚有关。例如，当网组（1，4）互连时，就有两个分区。一个分区包含管脚 2 和 3，另一个分区包含管脚5 ~8。**现在如果有一个网组，其两个管脚分别属于两个不同的分区，那么这个网组是不可布线的，进而整个开关盒布线实例也是不可布线的。**如果没有出现这样的网组，那么我们就可以根据连线不能跨区的原则，对每个分区是否可独立布线的问题做出判断。如果从一个分区中选择一个网组，这个网组把其所属分区分成两个子分区，而其余任一个网组的两个管脚都分属不同的子分区，那么就可以判断，这个分区是可布线的。

为了实现这个策略，可以从任意一个管脚开始，按顺时针或逆时针方向沿着开关盒的边界进行遍历。如果从管脚1 开始沿顺时针方向遍历图 8-8a 的管脚，那么遍历的管脚顺序是1，2，…，8。管脚1和4是一个网组，于是管脚1至4之间出现的所有管脚构成第一个分区，管脚4至1之间出现的所有管脚构成另一个分区。把管脚1插入栈，然后继续处理，直到管脚4。这个过程使我们仅在处理完一个分区之后才能进入下一个分区。下一个是管脚2，它与管脚 3 是一个网组，它们把当前分区分成两个分区。与前面的做法一样，把管脚 2 插入栈，然后继续处理，直到管脚3。由于管脚3和管脚2是一个网组，而管脚2正处在栈顶，因此这表明已经处理完一个分区，可将管脚 2 从栈顶删除。接下来将遇到管脚 4，而与它同是一个网组的管脚 1 正处在栈顶。现在，对一个分区的处理已经完毕，可从栈顶删除管脚 1。按照这种方法继续下去，我们可以完成对所有分区的处理，而且当 8个管脚都检查之后，栈为空。

代码

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

/*开关盒布线问题*/
/*确定开关盒是否可布线；数组net[0,n-1]管脚数组，用以形成网组；n是管脚个数*/
bool checkBox(int net[], int n)
{
    stack<int>* s = new stack<int>();
    //按顺时针扫描网组
    for (int i = 0; i < n; i++)
    {
        //处理管脚i
        if (!s->empty())
        {
            //检查栈的顶部管脚
            if (net[i] == net[s->top()])
                //管脚net[i]是可布线的，从栈中删除
                s->pop();
            else s->push(i);
        }
        else s->push(i);
    }
    //检查是否有剩余的不可布线的管脚
    if (s->empty())
    {
        //没有剩余的管脚
        cout << "Switch box is routable." << endl;
        return true;
    }
    else
    {
        //有剩余的管脚
        while(!s->empty()){
            cout << s->top() << " ";
            s->pop();
        }
        cout << endl << "Switch box is not routable." << endl;
        return false;
    }
}

int main()
{
    cout << "checkBox()**********************" << endl;
    int net[8] = { 1,2,2,1,3,3,4,4 };
    cout << "checkBox(net, 8) = " << endl;
    checkBox(net, 8);
    return 0;
}

运行结果

checkBox()**********************
checkBox(net, 8) =
Switch box is routable.

Process finished with exit code 0

标签：《数据结构算法与应用C++语言描述》-栈的应用-开关盒布线问题