Acwing2024蓝桥杯BFS

news/2024/12/23 0:42:32/

AcWing 1355. 母亲的牛奶

bfs: 

#include<iostream>
#include<queue>
using namespace std;
const int N=21;
int A,B,C;
bool flag[N][N][N];
struct node{int a,b,c;
};
queue<node>q;
void check(int a,int b,int c){if(!flag[a][b][c]){q.push({a,b,c});flag[a][b][c]=1;}
}
void bfs(){q.push({0,0,C});flag[0][0][C]=1;while(!q.empty()){auto t=q.front();q.pop();int a=t.a,b=t.b,c=t.c;check(a-min(a,B-b),min(a+b,B),c);check(a-min(a,C-c),b,min(a+c,C));check(min(a+b,A),b-min(b,A-a),c);check(a,b-min(b,C-c),min(c+b,C));check(min(a+c,A),b,c-min(c,A-a));check(a,min(b+c,B),c-min(c,B-b));}return ;
}
int main(){cin>>A>>B>>C;bfs();for(int c=0;c<=C;c++){for(int b=0;b<=B;b++){if(flag[0][b][c]){cout<<c<<" ";break;}}}return 0;
}

dfs:

#include<iostream>
using namespace std;
const int N=21;
int A,B,C;
bool flag[N][N][N];
void dfs(int a,int b,int c){if(flag[a][b][c]) return;flag[a][b][c]=1;dfs(a-min(a,B-b),min(a+b,B),c);dfs(a-min(a,C-c),b,min(a+c,C));dfs(min(a+b,A),b-min(b,A-a),c);dfs(a,b-min(b,C-c),min(c+b,C));dfs(min(a+c,A),b,c-min(c,A-a));dfs(a,min(b+c,B),c-min(c,B-b));return ;
}
int main(){cin>>A>>B>>C;dfs(0,0,C);for(int c=0;c<=C;c++){for(int b=0;b<=B;b++){if(flag[0][b][c]){cout<<c<<" ";break;}}}return 0;
}


AcWing 844. 走迷宫

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=110;
int n,m;
typedef pair<int,int>pii;
int mapp[N][N],d[N][N];
int bfs(){memset(d,-1,sizeof d);d[1][1]=0;queue<pii>q;q.push({1,1});int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};while(q.size()){auto t=q.front();q.pop();for(int i=0;i<4;i++){int x=t.first+dx[i],y=t.second+dy[i];if(x>=1&&x<=n&&y>=1&&y<=m&&d[x][y]==-1&&mapp[x][y]==0){d[x][y]=d[t.first][t.second]+1;q.push({x,y});}}}return d[n][m];
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>mapp[i][j];cout<<bfs()<<endl;return 0;
}


AcWing 845. 八数码

STL:unordered_map+bfs:

#include<iostream>
#include<unordered_map>
#include<queue>
using namespace std;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int bfs(string startt){string last="12345678x";//目标转态queue<string>q;//将字符串和数字联系在一起,字符串表示状态,数字表示距离unordered_map<string,int>d;//初始化q.push({startt});d[startt]=0;while(!q.empty()){auto t=q.front();//记录转态q.pop();int dist=d[t];//记录距离if(t==last) return dist;///终止状态//查找x在字符串中的下标,后转换为在矩阵中的坐标int k=t.find('x');int x=k/3,y=k%3;for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(xx>=0&&xx<3&&yy>=0&&yy<3){swap(t[k],t[xx*3+yy]);//交换,得到下一种状态if(!d.count(t)){//如果当前状态是第一次遍历,记录距离,入队d[t]=dist+1;q.push({t});}swap(t[k],t[xx*3+yy]);//还原状态}}}return -1;
}
int main(){string s;for(int i=0;i<9;i++){char ch;cin>>ch;s+=ch;}cout<<bfs(s)<<endl;return 0;
}


AcWing 1233. 全球变暖(第九届省赛)

这题在这篇文章里有具体写: 

三.搜索与图论(未完结)-CSDN博客

#include<iostream>
using namespace std;
const int N=1005;
char a[N][N],b[N][N];
int n,res,ans;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void dfs_all(int x,int y){b[x][y]='.';if(b[x-1][y]=='.'&&x-1>=0&&x-1<n&&y>=0&&y<n){if(b[x][y+1]=='.'&&x>=0&&x<n&&y+1>=0&&y+1<n){if(b[x+1][y]=='.'&&x+1>=0&&x+1<n&&y>=0&&y<n){if(b[x][y-1]=='.'&&x>=0&&x<n&&y-1>=0&&y-1<n){return ;}}}}for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(b[xx][yy]=='#'){dfs_all(xx,yy);}}
}
void dfs_rest(int x,int y){a[x][y]='.';if(a[x-1][y]=='.'&&x-1>=0&&x-1<n&&y>=0&&y<n){if(a[x][y+1]=='.'&&x>=0&&x<n&&y+1>=0&&y+1<n){if(a[x+1][y]=='.'&&x+1>=0&&x+1<n&&y>=0&&y<n){if(a[x][y-1]=='.'&&x>=0&&x<n&&y-1>=0&&y-1<n){return ;}}}}for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(a[xx][yy]=='*'||a[xx][yy]=='#'){dfs_rest(xx,yy);}}
}
int main(){cin>>n;for(int i=0;i<n;i++) for(int j=0;j<n;j++) {cin>>a[i][j];b[i][j]=a[i][j];}for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(b[i][j]=='#') {dfs_all(i,j);res++;}for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(a[i][j]=='.'){for(int k=0;k<4;k++){int x=i+dx[k],y=j+dy[k];if(a[x][y]=='#') a[x][y]='*';}}}}for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(a[i][j]=='#') {dfs_rest(i,j);ans++;}cout<<res-ans<<endl;return 0;
}

http://www.ppmy.cn/news/1462146.html

相关文章

【大数据】计算引擎MapReduce

目录 1.概述 1.1.前言 1.2.大数据要怎么计算&#xff1f; 1.3.什么是MapReduce&#xff1f; 2.架构 3.工作流程 4.shuffle 4.1.map过程 4.2.reduce过程 1.概述 1.1.前言 本文是作者大数据系列专栏的其中一篇&#xff0c;专栏地址&#xff1a; https://blog.csdn.ne…

Risk Of Rain 雨中冒险2服务器开服联机教程

1、购买后登录服务器&#xff08;百度莱卡云&#xff09; 1.1、第一次购买服务器会安装游戏端&#xff0c;大约5分钟左右&#xff0c;如果长时间处于安装状态请联系客服 2、设置游戏端口 由于雨中冒险2的设置需要两个端口&#xff0c;它们用于游戏端口&#xff0c;查询端口&am…

Jmeter使用While控制器

1.前言 对于性能测试场景中&#xff0c;需要用”执行某个事物&#xff0c;直到一个条件停止“的概念时&#xff0c;While控制器控制器无疑是首选&#xff0c;但是在编写脚本时&#xff0c;经常会出现推出循环异常&#xff0c;获取参数异常等问题&#xff0c;下面总结两种常用的…

AWS RDS ElasticCache 监控可观测最佳实践

在当今的电子商务时代&#xff0c;一个高效、稳定的电商平台对于保持竞争力至关重要。数据库作为电商平台的核心支撑&#xff0c;其性能直接影响到用户体验和业务流畅度。本文将深入探讨如何在电商场景下通过观测云对亚马逊云科技 RDS&#xff08;MySQL&#xff09; 和 Elastic…

MCULCD屏驱动方法

MCULCD屏驱动方式 一、LCD简介二、直接采用8080时序驱动LCD三、采用FSMC&#xff08;模拟8080时序&#xff09;驱动LCD1&#xff0c;FSMC简介2&#xff0c;结构框图3&#xff0c;FMC 驱动 LCD 显示配置步骤 一、LCD简介 Liquid Crystal Display&#xff0c;即液晶显示器&#…

Linux连接文件那点事

什么是连接文件 将一个文件和另一个文件建立联系&#xff0c;分为硬链接和软连接&#xff08;符号连接&#xff09;。 硬链接 Linux中&#xff0c;所有的文件都有一个inode&#xff0c;这个东西就是文件的ID号&#xff0c;硬链接的方式就是通过这个inode来产生新的文件名来建…

分析人工智能在智慧银行服务中的实际应用以及面临的挑战

一、引言 近年来,人工智能(AI)技术快速发展,其在金融领域,特别是智慧银行服务中的应用日益广泛。人工智能以其独特的数据处理能力、预测分析能力以及自动化决策能力,极大地提升了智慧银行的服务效率、降低了运营成本,并优化了客户体验。然而,人工智能在智慧银行服务中…

基础之音视频2

01 前言 02 mp 03 mp实例 简易音乐播放器 04 音频 sound-pool 1.作用 播放多个音频&#xff0c;短促音频 2.过程 加载load- 3.示例 模拟手机选铃声 步骤&#xff1a; 创建SoundPool对象&#xff0c;设置相关属性 音频流存入hashmap 播放音频 05 videoview 3gp 体积小 mp4 …