广度优先搜索练习感想

简介: 广度优先搜索练习感想

广搜的定义在此不再赘述,特别的,它非常适宜于解决“最少”这种发问的问题,一般由队列实现,我在锻炼的过程中也有了一些感悟。

首先广搜的问题是由迷宫问题引出的,这里设置两个增量数组比较简洁,从这里开始我就注意到广搜的分支其实比较容易写,关键在于这些数据如何存储和如何判重,解决了这两个,可能问题就比较清晰,下面是一些实例。


引、矩阵找块


题目: 求01矩阵中,一个位置上下左右是为相邻,若若干个1相邻,它们就构成了一个块,求块的个数

分析:这个题目其实用bfs和dfs均可以,其实和数据学图后找连通分量差不多。遍历矩阵所有点,如果遇到1采用bfs把这一块全部遍历,块数加一,注意遍历后应该标记以判重,这里由于矩阵不大,直接用两个二重数组存储矩阵和状态。

#include<iostream> 
#include<queue> 
using namespace std;
int dx[]={0,0,-1,1},dy[]={-1,1,0,0};
int a[15][15],count=0,n,m;
bool b[15][15];
struct node{
  int x,y;
};
node t,temp;
void bfs(node start){         //进入这个点为1点 ,广搜法 
  queue<node> q;
  q.push(start);
  while(!q.empty()){
  t=q.front();q.pop();
  for(int i=0;i<4;i++) {
  if(a[t.x+dx[i]][t.y+dy[i]]&&1<=t.x+dx[i]&&t.x+dx[i]
  <=m&&1<=t.y+dy[i]&&t.y+dy[i]<=n&&!b[t.x+dx[i]][t.y+dy[i]])
  {
    b[t.x+dx[i]][t.y+dy[i]]=1;
    temp.x=t.x+dx[i];
    temp.y=t.y+dy[i];
    q.push(temp);
  } 
  } 
  }
  count++;
}
void judge(){
  for(int i=1;i<=m;i++){
  for(int j=1;j<=n;j++)
  if(!b[i][j]&&a[i][j]){
  t.x=i;t.y=j;
  bfs(t);
  } 
}
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++)
  for(int j=1;j<=n;j++)
  scanf("%d",&a[i][j]);
  judge();
  printf("%d",count);
}


入门、8数码难题


题目: 初始状态的步数就算1,哈哈

输入:第一个33的矩阵是原始状态,第二个33的矩阵是目标状态。

输出:移动所用最少的步数

Input


2 8 3

1 6 4

7 0 5

1 2 3

8 0 4

7 6 5

Output

6


分析:题目问最少,显然bfs,这里如果用3*3的数组来表示每个状态,再入队出队可能比较占空间,实际上可以将每个状态转化为一个整数即可,再问如何判重?

1.想前面那样开个大数组空间可能不够,但是如果考虑到每个数只出现一次, 开两个9!大小的数组就够了,排好序后再二分查找下标,在另一个数组里判重

2.用map状态与步数一一对应

3.hash

这里其实看了大佬的7种方法思路,最终采用的是map+bfs解决

#include<iostream> 
#include<queue> 
#include<algorithm>
#include<map>
using namespace std;
map<int,int>s;
int end=0;
int x, y;
int dx[]={0,0,-1,1},dy[]={-1,1,0,0};
int a[4][4],b[4][4];
int change(){   //对状态进行转化 数组转数组 
  int sum=0;
  for(int i=1;i<4;i++)
  for(int j=1;j<4;j++)
  sum=sum*10+a[i][j];
  return sum;
}
void zhuanhua(int num)// 数字转数组 
{
  for(int i=3;i>0;i--)
  for(int j=3;j>0;j--)
  {
  a[i][j]=num%10;
  num=num/10;
  }
}
void bfs() {
  queue<int>q;
  int temp=change();
  s[temp]=1;
  if(temp==end){
  return;
  }
  q.push(temp);
  while(!q.empty()){
  temp=q.front();q.pop();
  zhuanhua(temp);
  for(int i=1;i<4;i++)
  for(int j=1;j<4;j++)
  {
    if(a[i][j]==0)
    {
    x=i;y=j;
    }
  }
  for(int i=0;i<4;i++) {
  if(1<=x+dx[i]&&x+dx[i]<=3&&1<=y+dy[i]&&y+dy[i]<=3)
  {  
      swap(a[x][y],a[x+dx[i]][y+dy[i]]);
      if(change()==end){
        s[change()]=s[temp]+1;
        return;
    }
  if(!s[change()]){
  q.push(change());
  s[change()]=s[temp]+1;
  }
  swap(a[x][y],a[x+dx[i]][y+dy[i]]);
  }
  }  
}
}
int main(){
  for(int i=1;i<4;i++)
  for(int j=1;j<4;j++)
  scanf("%d",&a[i][j]);
  for(int i=1;i<4;i++)
  for(int j=1;j<4;j++)
  scanf("%d",&b[i][j]);
  for(int i=1;i<4;i++)
  for(int j=1;j<4;j++)
  end=end*10+b[i][j];
  bfs();
  printf("%d",s[end]);  
}


这题反思比较多,无论是全排列+二分+bfs还是map+bfs,都将前面的知识给串起来了,对应这种压缩状态存储的理解也更深了一些。

这里可以开个结构体,0这个点的位置入栈,可以会省一些时间,由于我在Dev上通过了结果如下,而在codeup上编译错误我不太清楚错在哪里就没有细究:

1685016060149.jpg

之后我又做了一些题目,如魔块问题用把记录状态的数据就放在结点里,并用字符串储存过程,也有所收获。

相关文章
|
数据挖掘 开发工具 Python
基于Python开发的企业编码生成系统(源码+可执行程序+程序配置说明书+程序使用说明书)
基于Python开发的企业编码生成系统(源码+可执行程序+程序配置说明书+程序使用说明书)
179 0
|
传感器 数据可视化 机器人
Nvidia Isaac Sim图编程OmniGraph 入门教程 2024(6)
本文是Nvidia Isaac Sim图编程OmniGraph的入门教程,介绍了OmniGraph的概念、图的分类、以及如何利用ActionGraph创建可视化编程流程来控制仿真中的机器人动作和物体跟随,包括键盘控制小车的流程分析、Graph的创建、节点添加与连接,以及测试和Python实现方法。
859 0
|
存储 监控 物联网
Doris实时数仓
Doris实时数仓
811 11
|
Java 测试技术 容器
从零到英雄:Struts 2 最佳实践——你的Web应用开发超级变身指南!
【8月更文挑战第31天】《Struts 2 最佳实践:从设计到部署的全流程指南》深入介绍如何利用 Struts 2 框架从项目设计到部署的全流程。从初始化配置到采用 MVC 设计模式,再到性能优化与测试,本书详细讲解了如何构建高效、稳定的 Web 应用。通过最佳实践和代码示例,帮助读者掌握 Struts 2 的核心功能,并确保应用的安全性和可维护性。无论是在项目初期还是后期运维,本书都是不可或缺的参考指南。
136 0
|
Linux
Linux0.11 文件打开open函数(五)
Linux0.11 文件打开open函数(五)
136 0
|
数据采集 机器学习/深度学习 数据挖掘
python运用知识点说明
Python涵盖广泛,从基础语法(变量、数据类型、字符串操作)到高级特性(装饰器、迭代器、闭包)。常用库包括NumPy, Pandas(数据处理),Scikit-learn, TensorFlow(机器学习),Django, Flask(Web开发),Scrapy(网络爬虫)。应用于Web开发、数据分析、系统运维、游戏开发和网络爬虫。Python历经1.x、2.x到3.x版本,3.x引入重大更新,强调Unicode和函数打印等,与2.x不兼容。掌握这些能提升开发效率。【6月更文挑战第4天】
91 2
|
定位技术 iOS开发
在地图页面,自动布局控件开始是隐藏或在屏幕外需要正常显示时再为正常的显示状态的,需要在显示之前加入
在地图页面,自动布局控件开始是隐藏或在屏幕外需要正常显示时再为正常的显示状态的,需要在显示之前加入
128 0
typescript85-class组件类型
typescript85-class组件类型
116 0
typescript85-class组件类型
|
机器学习/深度学习 分布式计算 算法
如何从 8 个维度全面比较机器学习算法?
人类发明的机器学习(ML)算法简直数不胜数。当然,大多数时候只有一小部分被用于研究和工业。然而,对于个人来说,理解并记住所有这些 ML 模型的细节仍然有点困难。有些人可能会有一个错误的印象,认为所有这些算法都是完全不相关的。
|
算法 Linux 数据安全/隐私保护