Toggle navigation
首页
热门资讯
资源下载
技术博客
会员
中心
会员中心
发布博文
发布资源
首页
文章中心
C++
C++ 布线问题,分支限界法
100 阅读
0 评论
66 点赞
我是
靠谱客
的博主
贪玩篮球
,这篇文章主要介绍
C++ 布线问题,分支限界法
,现在分享给大家,希望可以做个参考。
#include <iostream>
#include <queue>
using
namespace
std;
int
m=8;
int
n=8;
int
grid[10][10];
int
indexcount=0;
struct
Position
{
int
row;
int
col;
};
void
showPath()
{
for
(
int
i=0; i<10; i++)
{
for
(
int
j=0; j<10; j++)
cout<<grid[i][j]<<
" "
;
cout<<endl;
}
cout<<
"------------------"
<<endl;
}
bool
FindPath(Position start,Position finish,
int
&PathLen,Position *&path)
{
//计算从起点位置start到目标位置finish的最短布线路径,找到最短布线路//径则返回true,否则返回false
if
((start.row==finish.row) && (start.col==finish.col))
{
PathLen=0;
cout<<
"start=finish"
<<endl;
return
true
;
}
//start=finish
//设置方格阵列“围墙”
//初始化图,-1为未访问
for
(
int
i=1; i<9; i++)
{
for
(
int
j=1; j<9; j++)
grid[i][j]=-1;
}
//添加阻挡点
grid[2][3]=-2;
for
(
int
i=0; i<= m+1; i++)
grid[0][i]=grid[n+1][i]=-2;
//顶部和底部
for
(
int
i=0; i<= n+1; i++)
grid[i][0]=grid[i][m+1]=-2;
//左翼和右翼
//初始化相对位移
cout<<
"完整图"
<<endl;
showPath();
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;
//上
int
NumOfNbrs=4;
//相邻方格数
Position here,nbr;
here.row=start.row;
here.col=start.col;
grid[start.row][start.col]=0;
//标记可达方格位置
cout<<
"布线前图"
<<endl;
showPath();
queue<Position> Q;
do
//标记相邻可达方格
{
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]==-1)
{
//该方格未被标记
//cout<<grid[nbr.row][nbr.col]<<endl;//显示路标值
grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;
//cout<<nbr.col<<" "<<nbr.row<<endl;//显示坐标
}
if
((nbr.row==finish.row) &&(nbr.col==finish.col))
break
;
//完成布线
Q.push(nbr);
}
//是否到达目标位置finish?
if
((nbr.row==finish.row)&&(nbr.col==finish.col))
break
;
//完成布线
//活结点队列是否非空?
if
(Q.empty())
return
false
;
//无解
here = Q.front();
//cout<<here.col<<" "<<here.row<<endl;
Q.pop();
//取下一个扩展结点
indexcount++;
// cout<<"下一节点"<<indexcount<<endl;
}
while
(
true
);
//构造最短布线路径
PathLen=grid[finish.row][finish.col];
path=
new
Position[PathLen];
//从目标位置finish开始向起始位置回溯
here=finish;
for
(
int
j=PathLen-1; j>=0; j--)
{
path[j]=here;
//找前驱位置
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]==j)
{
// cout<<j<<endl;
break
;
}
}
here=nbr;
//向前移动
}
return
PathLen;
}
int
main()
{
Position start;
start.col=1;
start.row=1;
cout<<
"布线起点"
<<endl;
cout<<start.col<<
" "
<<start.row<<endl;
Position finish;
finish.row=3;
finish.col=4;
cout<<
"布线结束点"
<<endl;
cout<<finish.col<<
" "
<<finish.row<<endl;
int
PathLen=0;
Position *path;
FindPath(start,finish,PathLen,path);
cout<<
"布线后路径图"
<<endl;
showPath();
cout<<
"路径"
<<endl;
for
(
int
i=0; i<PathLen; i++)
{
cout<<path[i].col<<
" "
<<path[i].row<<endl;
}
cout <<
"布线问题完毕!"
<< endl;
return
0;
}
最后
以上就是
贪玩篮球
最近收集整理的关于
C++ 布线问题,分支限界法
的全部内容,更多相关
C++
内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(
66
)
本文分类:
C++
浏览次数:
100
次浏览
发布日期:2023-11-15 16:05:03
本文链接:
https://www.kaopuke.com/article/k-p-k_13_u_23_o_14_f1_14_j_18_z.html
相关文章
解题报告:LightOJ - 1027 A Dangerous Maze 概率期望
迷宫问题——分支限界法
分支限界法求解迷宫问题分支限界法题目介绍总结
算法6.分支限界法下的迷宫游戏
C++ 布线问题,分支限界法
杭电OJ 1104(C++)
POJ3984—迷宫问题(bfs+ 打印路径)
牛牛走迷宫(bfs最短路)
评论列表
共有
0
条评论
发表评论
取消回复
登录
注册新账号
立即
投稿
返回
顶部
发表评论 取消回复