布线问题

标签: 算法分析与设计H

问题描述

印刷电路板将布线区域划分成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;
}
  • 如图

在这里插入图片描述

版权声明:本文为weixin_44307065原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44307065/article/details/106379509

智能推荐

1264页面推荐(中等 union all )稍微的难点在于找1的朋友

![在这里插入图片描述](https://img-blog.csdnimg.cn/20200904233840843.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTMxNTk0,size_16,color_FFFFFF,t...

单链表+单链表代码(链表最基础)

链表 链表是有顺序的表,在内存中存储: 链表是以节点的方式存储的 每个节点包括data域,next域:指向下一个节点 如图:发现链表的各个节点不一定是连续存放的,有跳跃的,不是连续存储 链表分为带头节点的链表和没有头结点的链表 添加: 1.先创建一个head头结点,作用就是单链表的头 2.后面每添加一个节点,就直接加入到链表最后 遍历: 代码 添加节点到链表里: 这里借助于temp节点,通过循环找...

Rtthread学习笔记(十三)RT-Thread Studio开启硬件看门狗Watchdog

一、开启硬件看门狗Watchdog 1、配置RT-Thread Settings 2、开启stm32f1xx_hal_conf.h中的宏定义 3.使用RT接口函数初始化硬件看门狗...

TYVJ 4864 天天去哪吃 || 清北学堂金秋杯大奖赛

题目描述: 记录一下i这个值上次出现的位置在哪里,就是pre...

java反编译

jvm 把Boolean类型的值flag当做int类型处理。​​​ Foo.java: 由 class 文件生成 jasm 文件:java -jar asmtools.jar jdis Foo.class > Foo.jasm  修改jasm文件: 执行反编译: java -jar jd-gui-1.6.6.jar File 打开Foo.class文件:b修改为2 重新执行java...

猜你喜欢

【学习笔记】03-v-html的学习和示例

v-html的认识和使用 示例: 显示结果: 注意:v-html是有复制的...

Java实现在线考试系统(系统介绍)

1.和现在有的考试系统有以下几种优势: a.和现在有的系统比较起来,本系统有科目、章节、老师、学生、班级等信息的管理,还有批阅试卷查看已批阅试卷等。传统的考试系统划分并不细,业务功能简单。 b.和学校的考试系统还有外面的考试系统比较起来,本系统是B/S结构,学校的考试系统一般为C/S结构,性能方面不如B/S结构,并且C/S接口需要安装客户端,客户端压力很大,我的系统只需要电脑具有浏览器,在同一局域...

计算机视觉--多视几何初步尝试

基础矩阵的原理 K和K’分别是两个相机的参数矩阵。p和p’是X在平面π的坐标表示。所以可以得出 具体计算过程 代码: #!/usr/bin/env python coding: utf-8 from PIL import Image from numpy import * from pylab import * import numpy as np from imp ...

java初学者怎么学习才可以快速入门

java初学者怎么学习才可以快速入门 一、了解JAVA 我们要知道:Java是由Sun Microsystems公司于1995年5月推出的Java面向对象程序设计语言。 Java之父:詹姆斯·高斯林 1.1 java的三个体系 Java SE(Java Platform Standard Edition)。Java SE 以前称为 J2SE。它允许开发和部署在桌面、服务器、嵌入式环境...

字段属性之主键&增删改查&自增长&唯一键约束

字段属性之主键&自增长&唯一键约束 主键 主键:primary key 主要的键 一张表中只有一个字段可以使用对应的键,用来唯一的约束该字段里面的数据,不能重复,这种称之为主键 一张表只能最多一个主键 增加主键 SQL操作中有多种方式增加主键大体分为三种 1.在创建表的时候直接在字段之后跟primary key关键字(主键本身不允许为空) 优点:非常直接:缺点:只能使用一个字段作为...