网站网址有哪些,快手点赞购买网站,php商城源码,岳阳网站建设的公司开关盒布线问题
问题描述
在开关盒布线问题中#xff0c;给定一个矩形布线区域#xff0c;其外围有若干管脚。两个管脚之间通过布设一条金属线路来连接。这条金属线路称为电线#xff0c;它被限制在矩形区域内。两条电线交叉会发生电流短路。因此#xff0c;电线不许交叉…开关盒布线问题
问题描述
在开关盒布线问题中给定一个矩形布线区域其外围有若干管脚。两个管脚之间通过布设一条金属线路来连接。这条金属线路称为电线它被限制在矩形区域内。两条电线交叉会发生电流短路。因此电线不许交叉。每对要连接的管脚称为一个网组。对于给定的一些网组我们需要确定它们能否连接而又不发生交叉。图 8-8a是一个布线的示例其中有8个管脚和4个网组。四个网组分别是142356和78。图8-8b的布线在网组14和23之间有交叉而图 8-8c的布线没有交叉。因为这 4 个网组的布线可以没有交叉所以这个开关盒称为可布线开关盒routable switch box。在现实问题中两个相邻的电线之间还要求保留一个最小的间隙但是我们忽略这个额外的要求。我们的问题是输入一个开关盒布线实例然后确定它是否可以布线。图8-8b和图8-8c的电线都是与x轴和y轴平行的直线段但与轴不平行的直线段或曲线段也是可以的。 求解策略
为了解决开关盒布线问题我们注意到当一个网组互连时连线把布线区域分隔成两个分区。分区边界上的管脚属于哪一个分区与连线无关而与互连网组的管脚有关。例如当网组14互连时就有两个分区。一个分区包含管脚 2 和 3另一个分区包含管脚5 ~8。**现在如果有一个网组其两个管脚分别属于两个不同的分区那么这个网组是不可布线的进而整个开关盒布线实例也是不可布线的。**如果没有出现这样的网组那么我们就可以根据连线不能跨区的原则对每个分区是否可独立布线的问题做出判断。如果从一个分区中选择一个网组这个网组把其所属分区分成两个子分区而其余任一个网组的两个管脚都分属不同的子分区那么就可以判断这个分区是可布线的。
为了实现这个策略可以从任意一个管脚开始按顺时针或逆时针方向沿着开关盒的边界进行遍历。如果从管脚1 开始沿顺时针方向遍历图 8-8a 的管脚那么遍历的管脚顺序是12…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)
{stackint* s new stackint();//按顺时针扫描网组for (int i 0; i n; i){//处理管脚iif (!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
