[董晓算法]搜索相关题目及模板

  前言：

本系列是学习了董晓老师所讲的知识点做的笔记

董晓算法的个人空间-董晓算法个人主页-哔哩哔哩视频 (bilibili.com)

 动态规划系列（还没学完）

【董晓算法】动态规划之线性DP问题-CSDN博客

【董晓算法】动态规划之背包DP问题（2024.5.11）-CSDN博客

【董晓算法】动态规划之背包DP与树形DP-CSDN博客

字符串系列（）

【董晓算法】竞赛常用知识之字符串1-CSDN博客

【董晓算法】竞赛常用知识之字符串2-CSDN博客

数据结构系列（未学完）

【董晓算法】竞赛常用知识点之数据结构1-CSDN博客

STL容器

​

图的存储

​

领接矩阵

应用:适用于点数不多的稠密图

int w[N][N];//边权 
int vis[N];
void dfs(int u){
  vis[u]=true;
  for(int v=1;v<=n;v++)
    if(w[u][v]){
      printf("%d,%d,%d\n",u,v,w[u][v]);
      if(vis[v]) continue;
      dfs(v);
    }
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    cin>>a>>b>>c;
    w[a][b]=c; 
  }
  dfs(1);
  return 0;
}

边集数组

​

应用:在 Kruskal算法中，需要将边按边权排序，直接存边

struct edge{
  int u,v,w;
}e[M];//边集 
int vis[N];
void dfs(int u){
  vis[u]=true;//标记为使用过
  for(int i=1;i<=m;i++)
    if(e[i].u==u){
      int v=e[i].v,w=e[i].w;
      printf("%d,%d,%d\n",u,v,w);
      if(vis[v]) continue;
      dfs(e[i].v);
    }
}        
int main(){
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    cin>>a>>b>>c;
    e[i]={a,b,c};//边的存储方式
    // e[i]={b,a,c};
  }
  dfs(1);
  return 0;
}

if(e[i].u==u)

作用：检查这条边的起始顶点 e[i].u 是否与当前正在考虑的顶点 u 相同

邻接表

​

出边数组e[u][i]存储u点的所有出边的{终点v,边权w}

struct edge{int v,w;};
vector<edge> e[N];//边集 
void dfs(int u,int fa){
  for(auto ed : e[u]){
    int v=ed.v, w=ed.w;
    if(v==fa) continue;
    printf("%d,%d,%d\n",u,v,w);
    dfs(v, u);
  } 
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=m;i++){ 
    cin>>a>>b>>c,
    e[a].push_back({b,c});
    e[b].push_back({a,c});
  }
  dfs(1, 0);
  return 0;
}

链式邻接表

​

边集数组 e[j] 存储第j条边的 {起点u,终点v,边权w]

表头数组 h[u][i] 存储u点的所有出边的编号

应用:各种图，能处理反向边

struct edge{int u,v,w;};
vector<edge> e;//边集
vector<int> h[N];//点的所有出边
void add(int a,int b,int c){
  e.push_back({a,b,c});
  h[a].push_back(e.size()-1);
}
void dfs(int u,int fa){
  for(int i=0;i<h[u].size();i++){
    int j=h[u][i];
    int v=e[j].v,w=e[j].w;
    if(v==fa) continue;
    printf("%d,%d,%d\n",u,v,w);
    dfs(v,u);
  }
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    cin>>a>>b>>c,
    add(a,b,c);
    add(b,a,c);
  }  
  dfs(1, 0);
  return 0;
}

 链式前向星

一个表头数组悬挂多个链表

边集数组 e[i]存储第i条出边的{终点v,边权w,下一条诀ne}

表头数组加存储u点的第一条出边的编号

边的编号 idx 可取 0,1,2,3 ..

​ 

struct edge{int v,w,ne;};
edge e[M];//边集
int idx,h[N];//点的第一条出边 
void add(int a,int b,int c){
  e[idx]={b,c,h[a]};
  h[a]=idx++;
}
void dfs(int u,int fa){
  for(int i=h[u];~i;i=e[i].ne){
    int v=e[i].v, w=e[i].w;
    if(v==fa) continue;
    printf("%d,%d,%d\n",u,v,w);
    dfs(v,u);
  }
}
int main(){
  cin>>n>>m;
  memset(h,-1,sizeof h);
  for(int i=1;i<=m;i++){
    cin>>a>>b>>c,
    add(a,b,c);
    add(b,a,c);
  }  
  dfs(1, 0);
  return 0;
}

DFS

int n, m, a, b, c;
vector<int> e[N];
void dfs(int u, int fa){
  for(auto v : e[u]){
    if(v==fa) continue;
    dfs(v, u);
  } 
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=m;i++)
    cin>>a>>b, 
    e[a].push_back(b),
    e[b].push_back(a);
  dfs(1, 0);
  return 0;
}

迷宫方案数

P1605 迷宫 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

​ 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 10;
int m,n,t,sx,sy,fx,fy,a,b,ans;
int g[N][N];
int dx[4]={-1,0,1, 0},dy[4]={ 0,1,0,-1};

void dfs(int x, int y){
  if(x==fx&&y==fy){ans++;return;}
  for(int i=0; i<4; i++){
    int a=x+dx[i], b=y+dy[i];//四个方位寻找
    if(a<1||a>n||b<1||b>m||g[a][b])continue;//退出条件
    g[a][b]=1; //锁定现场
    dfs(a, b);//递归
    g[a][b]=0; //恢复现场
  }    
}
int main(){
  cin>>n>>m>>t>>sx>>sy>>fx>>fy;
  for(int i=0;i<t;i++)cin>>a>>b, g[a][b]=1;
  g[sx][sy]=1;
  dfs(sx,sy);
  cout<<ans;
  return 0;
}

跳马方案数

P1644 跳马问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

学会设置偏移量(探照灯)
学会判越界，判重，回溯

int dx[4]={2,1,-1,-2};
int dy[4]={1,2, 2, 1};
void dfs(int x, int y){
  if(x==n&&y==m){ans++;return;}
  for(int i=0; i<4; i++){
    int a=x+dx[i], b=y+dy[i];
    if(a<0||a>n||b>m) continue;
    // printf("(%d,%d)\n",a,b);
    dfs(a,b);
  }    
}
void dfs(int x, int y){
  if(x==n&&y==m){ans++;return;}
  for(int i=0; i<4; i++){
    int a=x+dx[i], b=y+dy[i];//四个方位寻找
    if(a<0||a>n||b>m)continue;//退出条件
    dfs(a, b);//递归
  }    
}

八皇后

P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

学会按行搜索状态空间
学会标记对角线的技巧:p[i+j]，q[i-j+n]对角线与行列的映射关系

对角线技巧也可以通过列方程获得

int n, ans;
int pos[N],c[N],p[N],q[N];
void print(){
  if(ans<=3){//题目中只需要三个
    for(int i=1;i<=n;i++)
      printf("%d ",pos[i]);
    puts("");
  }
}
void dfs(int i){
  if(i>n){//终止条件
    ans++; print(); return;
  }
  for(int j=1; j<=n; j++){
    if(c[j]||p[i+j]||q[i-j+n])continue;//退出条件
    pos[i]=j; //记录第i行放在了第j列
    c[j]=p[i+j]=q[i-j+n]=1; //宣布占领
    dfs(i+1);
    c[j]=p[i+j]=q[i-j+n]=0; //恢复现场
  }
}
int main(){
  cin >> n;
  dfs(1);
  cout << ans;
  return 0;
}

水坑计数

判重技巧:节点变性

P1596 [USACO10OCT] Lake Counting S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

char g[N][N];
int dx[8]={-1,-1,-1,0,1,1,1,0};
int dy[8]={-1,0,1,1,1,0,-1,-1};

void dfs(int x,int y){
  g[x][y]='.';
  for(int i=0;i<8;i++){
    int a=x+dx[i],b=y+dy[i];
    if(a<0||a>=n||b<0||b>=m)continue;
    if(g[a][b]=='.')continue;
    dfs(a,b);
  }
}

BFS

vector<int> e[N];
int vis[N];
queue<int> q;

void bfs( ){
  vis[1]=1; q.push(1); //访问该点
  while(q.size()){//循环条件
    int x=q.front(); q.pop();//取对头元素
    for(auto y : e[x]){//遍历元素
      if(vis[y]) continue;//如果遍历过 就continue
      vis[y]=1; q.push(y);
    }
  }
}

迷宫最短路 

int n,g[N][N];
struct Node{int x,y;}; 
npde pre[N][N];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

void bfs (int x,int y){
  queue<Node> q;
  q.push({x,y});
  g[x][y] = 1;
  while(q.size()){
    auto u=q.front(); q.pop();
    for(int i = 0; i < 4; i ++){
      int a = u.x+dx[i],b = u.y+dy[i];
      if(a<0||a>=n||b<0||b>=n)continue;
      if(g[a][b])continue;
      g[a][b] = 1;//打标记
      pre[a][b] = u;//记录路径
      q.push({a,b});
    }        
  }
}
void print(int x,int y){
    if(x==0%%y==0) return;
    node p=pre[x][y];
    print(p.x,p.y);//递归
    printf("%d %d\n",x,y);
}
int main(){
  cin >> n;
  for(int i = 0; i < n; i ++)
    for(int j = 0; j < n; j ++)
      scanf("%d",&g[i][j]);
   bfs(0,0);
  puts("0 0");
  print(n-1,n-1);
  return 0;
}

矩阵距离-多源BFS问题

开始就把所有源头压入队列，其余同单源BFS问题一样。

char g[N][N];
struct Node{int x,y;};
int dis[N][N];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

void bfs(){
  memset(dis,-1,sizeof dis);
  queue<Node> q;
  for(int i=0; i<n; i++)
    for(int j=0; j<m; j++)
      if(g[i][j] == '1')
        dis[i][j]=0, q.push({i,j});
  while(q.size()){
    auto t=q.front(); q.pop();
    for(int i=0; i < 4; i++){
      int a=t.x+dx[i], b=t.y+dy[i];
      if(a<0||a>=n||b<0||b>=m)continue;
      if(dis[a][b]!=-1) continue;
      dis[a][b]=dis[t.x][t.y]+1;
      q.push({a,b});
    }
  }
}

DFS和BFS对比

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/630655.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

NSSCTF | [SWPUCTF 2021 新生赛]ez_unserialize

NSSCTF | [SWPUCTF 2021 新生赛]ez_unserialize

打开题目&#xff0c;发现是一个GIF动图页面&#xff0c;什么都没有。我们来查看一下源代码&#xff0c;看看有没有什么发现 其实只要足够了解网站的构成&#xff0c;看到绿色的注释字样就能知道它这里在提示robots.txt文件。 但是对于小白来说&#xff0c;也不知道它是什么&a…
阅读更多...
高效稳定，AH1515-15V转12V8A稳压芯片成为各种设备首选

高效稳定，AH1515-15V转12V8A稳压芯片成为各种设备首选

高效稳定&#xff0c;AH1515 15V转12V稳压芯片成为各种设备首选 随着科技的不断发展&#xff0c;各种电子设备对电源的要求越来越高&#xff0c;尤其是电压稳定性和电流输出能力。为了解决这一问题&#xff0c;我国一款名为AH1515的稳压芯片应运而生&#xff0c;凭借其优异的性…
阅读更多...
win11家庭中文版安装docker，报错 Docker Engine stopped

win11家庭中文版安装docker，报错 Docker Engine stopped

先引一下这位博主的链接超详细Windows11家庭中文版系统安装Docker-20230401_windows11安装docker-CSDN博客&#xff0c;我到前五步(跳出页面重启)和博主都是一样的&#xff0c;但是第六步我并没有报错&#xff0c;直接跳出docker界面 记录一下我的解决办法&#xff0c;首先按照…
阅读更多...
[链表专题]力扣141, 142

[链表专题]力扣141, 142

1. 力扣141 : 环形链表 题 : 给你一个链表的头节点 head &#xff0c;判断链表中是否有环。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了表示给定链表中的环&#xff0c;评测系统内部使用整数 pos 来表示链表尾…
阅读更多...
2024042001-计算机网络 - 物理层

2024042001-计算机网络 - 物理层

计算机网络 - 物理层 计算机网络 - 物理层 通信方式带通调制 通信方式 根据信息在传输线上的传送方向&#xff0c;分为以下三种通信方式&#xff1a; 单工通信&#xff1a;单向传输半双工通信&#xff1a;双向交替传输全双工通信&#xff1a;双向同时传输 带通调制 模拟信号…
阅读更多...
深度盘点解析一家公司的PMO的定位与发展规划

深度盘点解析一家公司的PMO的定位与发展规划

对于一家公司的PMO（项目管理办公室）的定位与发展规划，今天从以下几个方面进行深度盘点和解析，具体如下： 一、PMO的定位 1. 战略与推手：PMO是持续提升组织项目管理水平，实现组织所有项目成功的重要推手。它站在公司战略的高度，从全局视角出发，对公司内部的项目进行统一…
阅读更多...
使用高防IP是应对网络安全的重要措施

使用高防IP是应对网络安全的重要措施

使用高防IP&#xff08;High Defense IP&#xff09;在现代网络环境中显得尤为重要&#xff0c;这主要源于以下几个方面的原因&#xff1a; 一、网络安全形势严峻 随着互联网的快速发展&#xff0c;网络安全问题日益突出。各种网络攻击手段层出不穷&#xff0c;如分布式拒绝服…
阅读更多...
结合小波变换的遥感语义分割网络，融合频域和空间域特征提升分割效果

结合小波变换的遥感语义分割网络，融合频域和空间域特征提升分割效果

题目：SFFNet: A Wavelet-Based Spatial and Frequency Domain Fusion Network for Remote Sensing Segmentation 论文：http://arxiv.org/abs/2405.01992 代码：https://github.com/yysdck/SFFNet 年份：2024 创新点 两阶段网络SFFNet：网络首先使用空间方法提取特征，以保…
阅读更多...
论：即时战略RTS游戏的小地图采用 自下而上的汇报式 还是 自上而下的查找式？

论：即时战略RTS游戏的小地图采用 自下而上的汇报式 还是 自上而下的查找式？

关键词&#xff1a;RTS 小地图 游戏设计 思路 卫星 位置映射 阵营 更新 汇报 询问 UE4 UE5 Unreal Engine 前言 你是否想过类似红色警戒的战略小地图的要素是采用何种方式更新数据的。大量数据实时更新&#xff0c;考虑频率&#xff0c;运行效率&#xff0c;开发中如何选型&a…
阅读更多...
「每日跟读」英语常用句型公式 第15篇

「每日跟读」英语常用句型公式 第15篇

「每日跟读」英语常用句型公式 第15篇 1. It’s only logical that __ 合理的做法/结论是__ It’s only logical that we should take a break &#xff08;合理的做法是我们应该休息一下&#xff09; It’s only logical that we work hard to make money&#xff08;合理…
阅读更多...
SQL注入漏洞常用绕过方法

SQL注入漏洞常用绕过方法

SQL注入漏洞 漏洞描述 Web 程序代码中对于用户提交的参数未做过滤就直接放到 SQL 语句中执行&#xff0c;导致参数中的特殊字符打破了原有的SQL 语句逻辑&#xff0c;黑客可以利用该漏洞执行任意 SQL 语句&#xff0c;如查询数据、下载数据、写入webshell 、执行系统命令以及…
阅读更多...
详细分析Vue3中的ref（附Demo）

详细分析Vue3中的ref（附Demo）

目录 前言1. 基本知识2. Demo 前言 由于新项目涉及Vue3&#xff0c;本着探究问题的本质研究所不会的疑问 1. 基本知识 ref 是 Vue 3 中用于创建响应式数据的函数 接收一个初始值并返回一个包含了该值的响应式引用对象与 Vue 2.x 中的 data 属性不同&#xff0c;ref 返回的是…
阅读更多...
【JAVA入门】Day05 - 面向对象

【JAVA入门】Day05 - 面向对象

【JAVA入门】Day05 - 面向对象 文章目录 【JAVA入门】Day05 - 面向对象一、对象的设计和使用1.1 类和对象1.2 类的分类 二、封装三、private 关键字四、this 关键字五、构造方法六、JavaBean七、对象的内存图7.1 一个对象的内存图7.2 两个对象的内存图7.3 两个引用指向同一个对…
阅读更多...
一种请求头引起的跨域问题记录(statusCode = 400/CORS)

一种请求头引起的跨域问题记录(statusCode = 400/CORS)

问题表象 问题描述 当我们需要在接口的headers中添加一个自定义的变量的时候&#xff0c;前端的处理是直接在拦截器或者是接口配置的地方直接进行写&#xff0c;比如下面的这段比较基础的写法&#xff1a; $http({method: "post",url:constants.backend.SERVER_LOGIN…
阅读更多...
函数栈帧的创建和销毁（详细理解）

函数栈帧的创建和销毁（详细理解）

&#x1f381;个人主页&#xff1a;我们的五年 &#x1f50d;系列专栏&#xff1a;c语言课程学习 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 目录 问题&#xff1a; 1.ebp&#xff0c;esp两个寄存器用来维护函数栈帧 2.main函数也一个函数&#…
阅读更多...
QCustomPlot的了解

QCustomPlot的了解

&#xff08;一&#xff09;QCustomPlot常见属性设置、多曲线绘制、动态曲线绘制、生成游标、矩形放大等功能实现-CSDN博客 关键代码&#xff1a; QT core gui printsupport 使用上面文章中的代码跑起来的程序效果图&#xff1a; 我的学习过程&#xff1a; 最开始初…
阅读更多...
java 项目通用数据权限设计

java 项目通用数据权限设计

文章目录 前言一、常见的数据权限二、通用数据权限设计思路通用权限示例(灵活配置最简单方式)两个表业务理解最终拼接出来的sql 为: 总结 前言 权限一般分为操作权限和数据权限 操作权限: 菜单,页面,按钮 数据权限: 能看到的数据,包括各种页面的数据范围 一、常见的数据权限 …
阅读更多...
kafka用java收发消息

kafka用java收发消息

用java客户端代码来对kafka收发消息 具体代码如下 package com.cool.interesting.kafka;import org.apache.kafka.clients.consumer.ConsumerConfig; import org.apache.kafka.clients.consumer.ConsumerRecord; import org.apache.kafka.clients.consumer.ConsumerRecords; i…
阅读更多...
MP3解码入门（基于libhelix）

MP3解码入门（基于libhelix）

主要参考资料: 【Arduino Linux】基于 Helix 解码库实现 MP3 音频播放: https://blog.csdn.net/weixin_42258222/article/details/122640413 libhelix-mp3: https://github.com/ultraembedded/libhelix-mp3/tree/master 目录 一、MP3文件二、MP3 解码库三、libhelix-mp3库3.1 …
阅读更多...
Java 自然排序和比较器排序区别？Comparable接口和Comparator比较器区别？

Java 自然排序和比较器排序区别？Comparable接口和Comparator比较器区别？

注&#xff1a;如果你对排序不理解&#xff0c;请您耐心看完&#xff0c;你一定会明白的。文章通俗易懂。建议用idea运行一下案例。 1&#xff09;自然排序和比较器排序的区别&#xff1f; 自然排序是对象本身定义的排序规则&#xff0c;由对象实现 Comparable 接口&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023