中信建设官方网站,建设银行兰州分行网站,六站合一的优势,网站数据库连接错误《数据结构、算法与应用C语言描述》-队列的应用-电路布线问题
问题描述
在 迷宫老鼠问题中#xff0c;可以寻找从迷宫入口到迷宫出口的一条最短路径。这种在网格中寻找最短路径的算法有许多应用。例如#xff0c;在电路布线问题的求解中#xff0c;一个常用的方法就是在布…《数据结构、算法与应用C语言描述》-队列的应用-电路布线问题
问题描述
在 迷宫老鼠问题中可以寻找从迷宫入口到迷宫出口的一条最短路径。这种在网格中寻找最短路径的算法有许多应用。例如在电路布线问题的求解中一个常用的方法就是在布线区域设置网格该网格把布线区域划分成nxm个方格就像迷宫一样如图 9-12a 所示。一条线路从一个方格 a 的中心点连接到另一个方格 b 的中心点转弯处可以采用直角如图 9-12b 所示。已经有线路经过的方格被“封锁”成为下一条线路的障碍。我们希望用a 和 b之间的最短路径来布线以减少信号的延迟。
求解策略
a和b之间的最短路径需要在两个过程中确定。一个是距离标记过程另一个是路径标记过程。在距离标记过程中先从位置a开始把从a可到达的相邻方格都标记为1表示与a相距为1然后把从编号为1的方格可到达的相邻方格都标记为2表示与a相距为2。这个标记过程继续下去直至到达b或者没有可到达的相邻方格为止。图9-13a 显示了这种搜索过程的结果其中 a32b46。图中的阴影部分是被封锁的方格。
一旦到达 bb 的编号便是 b 与 a之间的距离在图 9-13a 中b上的标号为 9。距离标记过程结束之后路径标记过程开始。从方格 b 开始首先移动到一个其编号比b的编号小1的相邻方格上。在图9-13a中我们从b移到方格56。接下来从方格56移到比当前编号小 1 的相邻位置上。重复这个过程直至到达 a 为止。在图 9-13a 的例子中从56然后移到66、65、64、54等等。图 9-13b 给出了所得到的路径它是32和46之间的最短路径。注意最短路径不是唯一的32、33、43、53、54、64、65、66、56、46是另一条最短路径。
代码
#include iostream
#include queue
using namespace std;/*用于存储迷宫地址的结构体*/
struct Position
{int row, //行col; //列Position() {}Position(int prow, int pcol):row(prow),col(pcol){}operator int() const { return row; }friend ostream operator(ostream out, const Position x){out ( x.row , x.col );return out;}
};
/*创建二维数组*/
template class T
bool make2dArray(T** x, int numberOfRows, int numberOfColumns)
{try {//行指针x new T * [numberOfRows];//为每一行分配内存for (int i 0; i numberOfRows; i)x[i] new int[numberOfColumns];return true;}catch (bad_alloc) { return false; }
}/*遍历二维数组*/
templateclass T
void traverse2dArray(T** x, int numberOfRows, int numberOfColumns)
{for (int i 0; i numberOfRows; i){for (int j 0; j numberOfColumns; j){cout.width(4);cout x[i][j] ;}cout endl;}
}/*电路布线问题全局变量*/
int** Grid;//二维方阵
int GridSize;//方阵大小
queuePosition path;//记录路径的队列
/*电路布线---和迷宫老鼠问题有点像*/
/*方格元素为1表示为障碍方格元素为0表示无障碍*/
/*方格标记为2表示是起点方格标记为大于2的整数m表示该方格距离起点m-2步*/
void inputGridQueue()//输入迷宫
{cout Please enter the size of Grid-Matrix:;while (!(cin GridSize)){cin.clear();//清空标志位while (cin.get() ! \n)//删除无效的输入continue;cout Please enter the size of Grid-Matrix:;}//2的原因是为了避免在处理内部位置和边界位置时存在差别make2dArrayint(Grid, GridSize 2, GridSize 2);//初始化边界位置的数值for (int i 0; i GridSize 1; i){Grid[i][0] 1;Grid[0][i] 1;Grid[i][GridSize 1] 1;Grid[GridSize 1][i] 1;}//初始化迷宫for (int i 1; i GridSize; i)for (int j 1; j GridSize; j){int positionij;cout Please enter Grid[ i , j ]:;while (!(cin positionij)){cin.clear();//清空标志位while (cin.get() ! \n)//删除无效的输入continue;cout Please enter Grid[ i , j ]:;}Grid[i][j] positionij;}cout The Grid endl;traverse2dArrayint(Grid, GridSize 2, GridSize 2);
}
bool findPathQueue(Position start,Position end)//寻找从起点到终点的最短路径如找到返回true如没找到则返回false
{if ((start.row end.row) (start.col end.col))return true;//初始化偏移量Position offset[4];offset[0].row 0; offset[0].col 1;//右offset[1].row 1; offset[1].col 0;//下offset[2].row 0; offset[2].col -1;//左offset[3].row -1; offset[3].col 0;//上Position here start;Grid[start.row][start.col] 2;//标记起点为2int numOfNbrs 4;//一个方格的相邻位置数/*标记各个方格*/queuePosition q;//将需要标记的方格入栈qPosition nbr;//邻居方格while (true){//给相邻位置做标记for (int i 0; i numOfNbrs; i){nbr.row here.row offset[i].row;nbr.col here.col offset[i].col;if (Grid[nbr.row][nbr.col] 0)//只有方格为0时表示方格无障碍和未标记{Grid[nbr.row][nbr.col] Grid[here.row][here.col] 1;if ((nbr.row end.row) (nbr.col end.col))break;//如果标记到终点则标记完成q.push(nbr);//把邻居结点插入队列以备后面标记也就是找邻居的邻居}}if ((nbr.row end.row) (nbr.col end.col))break;//如果标记到终点则标记完成if (q.empty())return false;//没有找到终点则不可达返回falsehere q.front();//取队首元素作为下一节点以备标记其邻居节点q.pop();//删除队首节点}/*标记完成构造路径*/int pathLength Grid[end.row][end.col] - 2;here end;//从终点开始回溯for (int i pathLength - 1; i 0; i--){path.push(here);for (int j 0; j numOfNbrs; j)//在周边寻找父节点{nbr.row here.row offset[j].row;nbr.col here.col offset[j].col;if (Grid[nbr.row][nbr.col] i 2)break;}here nbr;}path.push(start);return true;
}
void outputPathQueue()//输出路径
{int i 0;cout The path ;while(!path.empty()){cout path.front() , ;path.pop();}cout endl;
}void routingOfCircuit()//测试函数
{inputGridQueue();//输入迷宫/*输入起始值点和终点*/Position start, end;cout Please enter the start node:;while (!(cin start.row start.col)){cin.clear();//清空标志位while (cin.get() ! \n)//删除无效的输入continue;cout Please enter the start node:;}cout Please enter the end node:;while (!(cin end.row end.col)){cin.clear();//清空标志位while (cin.get() ! \n)//删除无效的输入continue;cout Please enter the end node:;}findPathQueue(start, end);//寻找最短路径如找到返回true如没找到则返回falseoutputPathQueue();//输出路径
}int main()
{cout 电路布线问题******************** endl;routingOfCircuit();return 0;
}运行结果
C:\Users\15495\Documents\Jasmine\Work\coding\cmake-build-debug\coding.exe
鐢佃矾甯冪嚎闂********************
Please enter the size of Grid-Matrix:7
Please enter Grid[1,1]:0
Please enter Grid[1,2]:0
Please enter Grid[1,3]:1
Please enter Grid[1,4]:0
Please enter Grid[1,5]:0
Please enter Grid[1,6]:0
Please enter Grid[1,7]:0
Please enter Grid[2,1]:0
Please enter Grid[2,2]:0
Please enter Grid[2,3]:1
Please enter Grid[2,4]:1
Please enter Grid[2,5]:0
Please enter Grid[2,6]:0
Please enter Grid[2,7]:0
Please enter Grid[3,1]:0
Please enter Grid[3,2]:0
Please enter Grid[3,3]:0
Please enter Grid[3,4]:0
Please enter Grid[3,5]:1
Please enter Grid[3,6]:0
Please enter Grid[3,7]:0
Please enter Grid[4,1]:0
Please enter Grid[4,2]:0
Please enter Grid[4,3]:0
Please enter Grid[4,4]:1
Please enter Grid[4,5]:1
Please enter Grid[4,6]:0
Please enter Grid[4,7]:0
Please enter Grid[5,1]:1
Please enter Grid[5,2]:0
Please enter Grid[5,3]:0
Please enter Grid[5,4]:0
Please enter Grid[5,5]:1
Please enter Grid[5,6]:0
Please enter Grid[5,7]:0
Please enter Grid[6,1]:1
Please enter Grid[6,2]:1
Please enter Grid[6,3]:1
Please enter Grid[6,4]:0
Please enter Grid[6,5]:0
Please enter Grid[6,6]:0
Please enter Grid[6,7]:0
Please enter Grid[7,1]:1
Please enter Grid[7,2]:1
Please enter Grid[7,3]:1
Please enter Grid[7,4]:0
Please enter Grid[7,5]:0
Please enter Grid[7,6]:0
Please enter Grid[7,7]:0
The Grid 1 1 1 1 1 1 1 1 11 0 0 1 0 0 0 0 11 0 0 1 1 0 0 0 11 0 0 0 0 1 0 0 11 0 0 0 1 1 0 0 11 1 0 0 0 1 0 0 11 1 1 1 0 0 0 0 11 1 1 1 0 0 0 0 11 1 1 1 1 1 1 1 1
Please enter the start node:3 2
Please enter the end node:4 6
The path (4,6), (5,6), (6,6), (6,5), (6,4), (5,4), (5,3), (5,2), (4,2), (3,2),Process finished with exit code 0离线等价类问题
