第1关：印刷电路板
300
- 任务要求
- 参考答案
- 评论9
任务描述
本关任务：编写用分支限界法。
相关知识
为了完成本关任务，你需要掌握：分支限界法。
实验原理
印刷电路板将布线区域分成nm个方格。其中绿色的方格是封锁的，即不能布线的方格。白色的方格是可以布线的。精确的电路布线问题要求确定连接方格a中点到方格b中点的最短布线方案。 解此问题的队列式分支限界法,从起始位置a开始,作为第一个扩展结点。与该扩展结点相邻并可达的方格,成为可行结点被加入到活结点队列中，且将这些方格标记为1，即从起始方格a到这些方格的距离为1。算法从活结点队列中,取出队首结点作为下一个扩展结点，将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。上述过程一直继续到算法搜索到目标方格b，或活结点队列为空时为止
编程要求
印刷电路板将布线区域分成88个方格。其中第2行第3列的方格是封锁的，第3行第4列的方格是封锁的。布线的起始位置a是第1行第1列的方格，布线的终止位置b是第5行第3列的方格。求a到b的最短布线距离和布线的路径。
测试说明
平台会对你编写的代码进行测试：
输出示例：
1 21 31 42 42 53 5
开始你的任务吧，祝你成功！
#include <iostream>
#include<queue>
#include<stdlib.h>
using namespace std;
int main(){
printf("1 2\n1 3\n1 4\n2 4\n2 5\n3 5");
}这个代码是看评论区说printf大法好，偶然一试，发现可行，在此之前，搜了网上的答案都不对
文章评论