布线问题

问题描述

印刷电路板将布线区域划分成nXm个方格阵列。精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线。为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。

现给定起始点位置，求出一条从起点到终点的最短路径。

算法思想

• 广度搜索
• 用二维数组表示网格，并且在网格的外围预处理一层“墙壁”，初始化为-1，表示不通
• 网格grid[i][j]存储从起点开始到达（i，j）的步长也就是层数
• 用两个数组表示搜索方向：

int offsetX[4]={ 
   0,1,0,-1};
int offsetY[4]={ 
   1,0,-1,0};

• 在搜索过程中如果子节点的值为0表示可以搜索
• 到达终点后回溯从终点开始搜寻一条到达起点的路径，由grid[i][j]可以扩展出4子节点，判断子节点的步长是否为父节点步长-1若是，则表示由子节点扩展而来

实现代码

#include <iostream>
#include <queue>
#include <windows.h>
using namespace std;
int m;
int n;
int grid[1002][1002]={ 
   0};
int indexCount=0;
//移动方向
int offsetX[4]={ 
   0,1,0,-1};
int offsetY[4]={ 
   1,0,-1,0};
struct Position
{ 
   
    int x;
    int y;
    Position(int xx=0,int yy=0):x(xx),y(yy){ 
   };
};
void findPath(Position finish,int pathLen,Position* path)
{ 
   
    path=new Position[pathLen];
    Position here=finish;
    for(int i=pathLen-1;i>0;i--)
    { 
   
        path[i]=here;
        int xx,yy;
        for(int j=0;j<4;j++)
        { 
   
            xx=here.x+offsetX[j];
            yy=here.y+offsetY[j];
            if(grid[xx][yy]==i) break;//父节点的布线长度,为i即当前长度减一
        }
        here.x=xx;
        here.y=yy;
    }
}
bool takeLine(Position start,Position finish,int &pathLen,Position* path)
{ 
   
    if(start.x==finish.x&&start.y==finish.y)
    { 
   
        pathLen=0;
        cout<<"start=finish"<<endl;
        return true;
    }
    //预处理边界
    for(int i=0;i<=m+1;i++)
        grid[0][i]=grid[n+1][i]=-1;
    for(int j=0;j<=n+1;j++)
        grid[j][0]=grid[j][m+1]=-1;      
    queue<Position>Q;
    //根节点入队列
    Q.push(start);
    grid[start.x][start.y]=1;
    while(!Q.empty())
    { 
   
        Position q=Q.front();
        Q.pop();
        for(int i=0;i<4;i++)
        { 
   
            int xx=q.x+offsetX[i];
            int yy=q.y+offsetY[i];
            if(grid[xx][yy]==0) //当子节点合法
            { 
   
                grid[xx][yy]=grid[q.x][q.y]+1;
                Q.push(Position(xx,yy)); //子节点入队列
                if(xx==finish.x&&yy==finish.y)//找到终点
                { 
   
                    pathLen=grid[finish.x][finish.y];
                    findPath(finish,pathLen,path);
                    return true;
                }
            }
        }
    }
    return false;
}
int main()
{ 
   
    cin>>m>>n;//输入规模
    Position start,finish;
    cin>>start.x>>start.y>>finish.x>>finish.y;//起始点个终止点
    int num;
    cin>>num;
    for(int i=0;i<num;i++)
    { 
   
        int x,y;
        cin>>x>>y;
        grid[x][y]=-1;
    }
    int pathLen=0;    //路长
    Position* path=NULL; //路径
    takeLine(start,finish,pathLen,path);
    cout<<pathLen;
    for(int i=0;i<pathLen;i++)
        printf("[%d,%d]\n",path[i].x,path[i].y);
    system("pause");
    return 0;
}
/* 7 7 3 2 4 6 14 1 3 2 3 2 4 3 5 4 4 4 5 5 1 5 5 6 1 6 2 6 3 7 1 7 2 7 3 */

算法时间复杂度

由于扩展中每一个节点可以扩展4次，所以最多要进行4^N次搜索，因此时间复杂度为T(n)=O(4^N)

debug

在敲代码的时候遇到了一个关于内存分配的问题，函数原型如下

• 函数func1在内部分配内存，将p指向一块int5大小的内存，但是在main函数外面的p指针却无法访问该内存
• 函数func2在内部分配内存之后将指针返回，在main函数外部的指针q则可以访问该内存

#include <iostream>
using namespace std;
void func1(int *p)
{ 
   
    p=new int[5];
    for(int i=0;i<5;i++) p[i]=i;
}
int* func2()
{ 
   
    int* p=new int[5];
    for(int i=0;i<5;i++) p[i]=i;
    return p;
}
int main()
{ 
   
    int* p=NULL;
    int* q=NULL;
    
    func1(p);
    for(int i=0;i<5;i++) printf("%d ",p[i]);//出错
    
    q=func2();
    for(int i=0;i<5;i++) printf("%d ",q[i]);
    
    system("pause");
    return 0;
}

• 如图

今天的文章布线问题分享到此就结束了，感谢您的阅读。