首页 > 其他分享 >BFS 2025/1/16

BFS 2025/1/16

时间：2025-01-16 16:48:03浏览次数：1  
标签：yy 16 int tt st BFS 2025 xx 10 

BFS

Basic 
主要特点:空间复杂度较高,基于队列 
经常用于求最优解的搜索题
经典模型:连通块,最短迷宫路径,曼哈顿距离
 
 
Question 01 [ACP2056 山峰与山谷] 
主体是广搜模板
难点在于如何判断当前联通块是山峰或山谷
考虑在广搜时进行维护
如果 BFS 检测到的区域不是在当前连通块
就判断其与当前连通块高度的大小关系 
进而判断当前连通块是山峰或山谷
注意要先判断大小关系再判断标记数组
(显而易见但一写就 WA ) 

Code
#include<bits/stdc++.h>
using namespace std;
const int N=1024,dx[10]={0,1,1,1,0,0,-1,-1,-1},dy[10]={0,1,0,-1,1,-1,1,0,-1};
int n,mp[N][N],top,bottom,ff,tt;
bool st[N][N],istop,isbottom;
struct Point{int x,y;}k[N*N];
void bfs(int sx,int sy){
	ff=1,tt=0;
	k[++tt]={sx,sy};
	st[sx][sy]=true;
	while(ff<=tt){
		int x=k[ff].x,y=k[ff++].y;
		for(int i=1;i<=8;i++){
			int xx=x+dx[i];
			int yy=y+dy[i];
			if(xx<1||yy<1||xx>n||yy>n)continue;
			if(mp[xx][yy]>mp[x][y]){
				istop=0;
				continue;
			}else if(mp[xx][yy]<mp[x][y]){
				isbottom=0;
				continue;
			}
			if(st[xx][yy])continue;
			st[xx][yy]=true;
			k[++tt]={xx,yy};
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&mp[i][j]);
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
		if(st[i][j])continue;
		istop=1,isbottom=1;
		bfs(i,j);
		if(istop)++top;
		if(isbottom)++bottom;
	}
	printf("%d %d\n",top,bottom);
	return 0;
} 


Question 02 [ACP9084 武士风度的牛] 
BFS 模板题
重点调一下方向偏差值数组即可

Code
#include<bits/stdc++.h>
using namespace std;
const int N=160,dx[10]={0,2,2,1,1,-1,-1,-2,-2},dy[10]={0,1,-1,2,-2,2,-2,1,-1};
int n,m,ff,tt,fx,fy,sx,sy;
char mp[N][N];
bool st[N][N];
struct Point{int x,y,step;}k[N*N];
int bfs(){
	ff=1,tt=0;
	k[++tt]={sx,sy,0};
	st[sx][sy]=true;
	while(ff<=tt){
		int x=k[ff].x,y=k[ff].y,step=k[ff++].step+1;
		for(int i=1;i<=8;i++){
			int xx=x+dx[i],yy=y+dy[i];
			if(xx<1||yy<1||xx>n||yy>m)continue;
			if(st[xx][yy])continue;
			if(mp[xx][yy]=='*')continue;
			if(xx==fx&&yy==fy)return step;
			st[xx][yy]=true;
			k[++tt]={xx,yy,step};
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	swap(n,m);
	for(int i=1;i<=n;i++){
		scanf("%s",mp[i]+1);
		for(int j=1;j<=m;j++){
			if(mp[i][j]=='K')sx=i,sy=j;
			if(mp[i][j]=='H')fx=i,fy=j;
		}
	}
	printf("%d",bfs());
	return 0;
}


Question [ACP1912 迷宫]
题面就是裸的迷宫板子
思考如何输出路径
考虑记录每一状态前驱的队列下标
递归到达开始状态
在 return 的过程中输出即可

Code
#include<bits/stdc++.h>
using namespace std;
int mp[6][6],dx[6]={0,1,0,-1,0},dy[6]={0,0,1,0,-1},ff,tt;
bool st[6][6];
struct node{int x,y,previd;}k[30];
void print(int id){
	if(id==-1)return;
	print(k[id].previd);
	printf("(%d, %d)\n",k[id].x-1,k[id].y-1);
}
void dfs(int sx,int sy,int fx,int fy){
	ff=1,tt=0;
	k[++tt]={sx,sy,-1};
	st[sx][sy]=true;
	while(ff<=tt){
		int x=k[ff].x,y=k[ff++].y;
		for(int i=1;i<=4;i++){
			int xx=x+dx[i],yy=y+dy[i];
			if(xx<1||yy<1||xx>5||yy>5)continue;
			if(st[xx][yy])continue;
			if(mp[xx][yy])continue;
			st[xx][yy]=true;
			k[++tt]={xx,yy,ff-1};
			if(xx==fx&&yy==fy){
				print(tt);
				return;
			}
		}
	}
}
int main(){
	for(int i=1;i<=5;i++)for(int j=1;j<=5;j++)scanf("%d",&mp[i][j]);
	dfs(1,1,5,5);
	return 0;
}


Question 04 [ACP2520 矩阵距离]
曼哈顿距离模板
将 value 为一的位置入队列
标记 step 即可
ans 数组可与标记数组结合
 
Code
#include<bits/stdc++.h>
using namespace std;
const int N=1012,dx[6]={0,1,0,0,-1},dy[6]={0,0,1,-1,0};
int n,m,mp[N][N],ff=1,tt=0,st[N][N];
struct Point{int x,y,step;}k[N*N];
int main(){
	scanf("%d%d",&n,&m);
	char input[N];
	for(int i=1;i<=n;i++){
		scanf("%s",&input);
		for(int j=1;j<=m;j++){
			mp[i][j]=input[j-1]-'0';
			if(mp[i][j])k[++tt]={i,j,0},st[i][j]=-1;
		}
	}
	while(ff<=tt){
		int x=k[ff].x,y=k[ff].y,step=k[ff++].step+1;
		for(int i=1;i<=4;i++){
			int xx=x+dx[i],yy=y+dy[i];
			if(xx<1||yy<1||xx>n||yy>m)continue;
			if(st[xx][yy]!=0)continue;
			st[xx][yy]=step;
			k[++tt]={xx,yy,step};
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)printf("%d ",(st[i][j]==-1)?0:st[i][j]);
		puts("");
	}
	return 0;
} 

Question 05[ACP2060 魔板] 
本题仍然是明确的 BFS
有明确的转移
难点在于记录状态
本题采用 int 进行存储
写出对应的 A,B,C 函数
 
Code
#include<bits/stdc++.h>
using namespace std;
const int ten[10]={1,10,100,1000,10000,100000,1000000,10000000};
struct node{int key,step,previd,way;}k[100000];
inline int A(int k){return (k/10000)+(k%10000)*10000;}
inline int B(int k){
	int ll=k/10000,rr=k%10000;
	ll=(ll%10)*1000+ll/10;
	rr=(rr%10)*1000+rr/10;
	return ll*10000+rr;
}
inline int C(int k){
	int a=k/ten[7]%10;
	int b=k/ten[6]%10;
	int c=k/ten[5]%10;
	int d=k/ten[4]%10;
	int e=k/ten[3]%10;
	int f=k/ten[2]%10;
	int g=k/ten[1]%10;
	int h=k/ten[0]%10;
	return a*ten[7]+f*ten[6]+b*ten[5]+d*ten[4]+e*ten[3]+g*ten[2]+c*ten[1]+h;
}
map<int,int> st;
char ans[2009];
int cnt=0;
void show(int id){
	if(k[id].previd==-1)return;
	show(k[id].previd);
	ans[++cnt]=(char)k[id].way;
}
void bfs(int sx,int fx){
	int ff=1,tt=0;
	k[++tt]={sx,0,-1,-1};
	st[sx]=114514;
	while(ff<=tt){
		int key=k[ff].key,previd=ff,step=k[ff++].step+1;
		int a=A(key),b=B(key),c=C(key);
		if(st[a]!=114514){
			st[a]=114514;
			k[++tt]={a,step,previd,(int)'A'};
			if(a==fx){
				printf("%d\n",step);
				show(tt);
				return;
			}
		}
		if(st[b]!=114514){
			st[b]=114514;
			k[++tt]={b,step,previd,(int)'B'};
			if(b==fx){
				printf("%d\n",step);
				show(tt);
				return;
			}
		}
		if(st[c]!=114514){
			st[c]=114514;
			k[++tt]={c,step,previd,(int)'C'};
			if(c==fx){
				printf("%d\n",step);
				show(tt);
				return;
			}
		}
	}
}
int main(){
	st.clear();
	int t=0,x,lable[10];
	for(int i=1;i<=8;i++)scanf("%d",&lable[i]);
	t=lable[1]*ten[7]+lable[2]*ten[6]+lable[3]*ten[5]+lable[4]*ten[4]+lable[8]*ten[3]+lable[7]*ten[2]+lable[6]*ten[1]+lable[5]*ten[0];
	if(t==12348765)puts("0"),exit(0);
	bfs(12348765,t);
	for(int i=1,it=1;i<=cnt;i++,it++){
		putchar(ans[i]);
		if(it==60)it=0,puts("");
	}
	return 0;
} 

Question 06 [ACP2059 电路维修]
毒瘤题! 
本题转移是向四角
重点是电力点其实是在格点上
所以向四周转移是有两种情况
一种是需要拧一下电路
另一种是不需要拧 
所以有时可能会导致 step 加一
也有可能不变
所以就不能保证先搜到的一定是答案
本题用到了 Dijstra 思想
用当前最小去松弛其转移点 
Code
#include<bits/stdc++.h>
using namespace std;
const int N=507,dx[7]={0,1,1,-1,-1},dy[7]={0,-1,1,-1,1};
char mp[N][N]={};
bool st[N][N];
int n,m;
struct node{
	int x,y,step;
};
bool able(int x,int y,int id){
	if(id==1)return mp[x+1][y]=='/';
	if(id==2)return mp[x+1][y+1]=='\\';
	if(id==3)return mp[x][y]=='\\';
	if(id==4)return mp[x][y+1]=='/';
	puts("Shit!");
	return 0;
}
deque<node> q;
int bfs(int sx,int sy){
	q.clear();//初始化 
	st[sx][sy]=true;
	q.push_front({sx,sy,0});
	while(!q.empty()){
		int x=q.front().x,y=q.front().y,step=q.front().step; 
		q.pop_front(); 
		st[x][y]=true;
		if(x==n&&y==m)return step;
		for(int i=1;i<=4;i++){
			int xx=x+dx[i],yy=y+dy[i];
			if(xx<0||yy<0||xx>n||yy>m)continue;
			if(st[xx][yy])continue;
			if(able(x,y,i))q.push_front({xx,yy,step});
			else q.push_back({xx,yy,step+1});
		}
	}
	puts("Fuck!");
	return 0;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)st[i][j]=false; 
		for(int i=1;i<=n;i++)scanf("%s",mp[i]+1);
		if((n+m)%2==1)puts("NO SOLUTION");
		else if(n+m==0)puts("0");
		else printf("%d\n",bfs(0,0));
	}
	return 0;
}

标签：yy,16,int,tt,st,BFS,2025,xx,10
From： https://www.cnblogs.com/2025ing/p/18675244

相关文章

  • 2025年实战技巧！如何通过项目管理助力产品经理实现产品目标？
    在当今竞争激烈的商业环境中，产品经理不仅要负责产品的整体规划和设计，还需要确保项目能够按时、按质、按预算完成。这就需要产品经理具备出色的项目管理能力。本文将深入探讨如何通过项目管理助力产品经理实现产品目标，并提供2025年的实战技巧。引言随着市场的不断变化和技术的......
  • pkuwc 2025 游记
    Day-1课表上写的上午自主补题，下午休息，于是上午偷偷划水，下午光明正大划水（，下午划水的时候没绷住被06击杀，除了我还有六个，有点抽象。晚上@Ricefruit再一次被06击杀罚站30min，回来的时候@Ricefruit没绷住让06看到了标签页上@fangzichang大神的休息论，于是晚上我们几个又被......
  • 2025四款简单好用的电脑便签提醒软件推荐
    进入2025年，越来越多的打工人需要在电脑上使用一款桌面便签或日程提醒软件，随时记录和管理工作事项，能够帮助我们高效整理思绪，确保重要事务不被遗漏。今天给大家介绍四款简单又好用的电脑便签或日程提醒软件，总有一款是适合你的！一、Win系统便笺Windows操作系统自带的轻量级便笺工具......
  • 2025年环境工程与低碳发展国际会议（EELCD 2025）
    The2ndInternationalConferenceonEnvironmentalEngineeringandLowCarbonDevelopment一、大会信息会议简称：EELCD2024投稿邮箱：eelcd@sub-paper.com大会地点：中国·银川收录检索：提交EiCompendex,CPCI,CNKI,GoogleScholar等二、会议简介备受瞩目的第二届环境......
  • 2025年心理健康、教育与艺术传播国际会议（MHEAC 2025）
    20252thInternationalConferenceonMentalHealth,Education,andArtCommunication一、【会议简介】        即将在人间天堂杭州拉开帷幕的第二届心理健康、教育与艺术传播国际会议，是一场旨在深化全球心理健康、教育创新及艺术传播领域交流与合作的学术盛宴。......
  • 使用Python爬虫获取1688网站item_get_company API接口的公司档案信息
    一、引言在当今的商业环境中，获取供应商的详细信息对于采购决策、市场分析和供应链管理至关重要。1688作为中国领先的B2B电子商务平台，提供了丰富的供应商档案信息。通过使用1688的item_get_companyAPI接口，我们可以方便地获取这些信息。本文将详细介绍如何使用Python爬虫来调用该A......
  • 使用Python爬虫获取1688网站实力档案信息
    引言1688是阿里巴巴旗下的B2B电子商务平台，提供了丰富的商品和供应商信息。为了获取供应商的实力档案信息，我们可以使用1688的API接口item_get_strength。本文将详细介绍如何使用Python爬虫来调用该API并获取所需信息。环境准备在开始之前，请确保你的系统已经安装了以下工具和库：......
  • 利用Python爬虫按图搜索1688商品（拍立淘）的探索之旅
    在当今这个信息爆炸的时代，网购已成为人们生活中不可或缺的一部分。而1688作为国内知名的B2B电商平台，汇聚了海量的商品资源。当我们面对琳琅满目的商品时，传统的文字搜索方式有时会显得力不从心。比如，当你看到一件心仪的商品图片，却不知道该如何用文字准确描述它来搜索时，就会陷入......
  • 2025年Java面试八股文合集（持续更新）
    1、并行与并发的区别并发是同一时间处理多件事的能力，比如多个线程轮流使用一个CPU并行是同一时间做多件事的能力，比如4核CPU同时执行4个线程关键区别在于是否同时执行2、创建线程的方式有哪几种？Runnable与Callable有什么区别？run方法与start方法有什么区别继承Tread类——......
  • 上交2025最新-《动手学大模型》实战教程及ppt分享！
    本课介绍今天分享一个上海交大的免费的大模型课程，有相关教程文档和Slides，目前是2.2K星标，还是挺火的！《动手学大模型》系列编程实践教程，由上海交通大学2024年春季《人工智能安全技术》课程（NIS3353）讲义拓展而来（教师：张倬胜），旨在提供大模型相关的入门编程参考。通过简单实践，帮......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99