2024算法基础公选课练习七(BFS1)

embedded/2024/11/28 14:22:54/

一、前言

还是偏基础的bfs,但是有几个题不是很好写

二、题目总览

三、具体题目

3.1 问题 A: 数据结构-队列-奇怪的电梯

我的代码

可以看成求一维平面的bfs最短路

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;
std::vector<int> a(N,0);
std::vector<bool> vis(N,false);int n,st,ed;void bfs(){std::queue<pii> q;vis[st] = true;pii p;p.first = st,p.second = 0;q.emplace(p);while(!q.empty()){auto t = q.front();q.pop();if(t.first==ed){std::cout << t.second << '\n';return;}pii t1,t2;t1.first = t.first+a[t.first];t1.second = t.second+1;if(t1.first<=n&&!vis[t1.first]){vis[t1.first] = true;q.emplace(t1);}t2.first = t.first-a[t.first];t2.second = t.second+1;if(t2.first>=1&&!vis[t2.first]){vis[t2.first] = true;q.emplace(t2);}}std::cout << "-1\n";
}void solve(){std::cin >> n >> st >> ed;for(int i = 1;i<=n;++i) std::cin >> a[i];bfs();}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.2 问题 B: 连通块

我的代码

找全是1的联通块个数,直接枚举每个点bfs(当前未访问过的点)即可

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e2+5,M = 1e6+5,INF = 0x3f3f3f3f;
int n,m;
int g[N][N];
bool vis[N][N];
int ans;
using node = std::array<int,3>;
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
void bfs(int sx,int sy){std::queue<node> q;node t;t[0] = sx,t[1] = sy,t[2] = 0;q.emplace(t);vis[sx][sy] = true;++ans;while(!q.empty()){auto t = q.front();q.pop();for(int i = 0;i<4;++i){int u = t[0]+dx[i],v = t[1]+dy[i];if(u<1||u>n||v<1||v>m||vis[u][v]||g[u][v]==0) continue;node t1;vis[u][v] = true;t1[0] = u,t1[1] = v,t1[2] = t[2]+1;q.emplace(t1);}}
}
void solve(){std::cin >> n >> m;for(int i = 1;i<=n;++i){for(int j = 1;j<=m;++j){std::cin >> g[i][j];}}for(int i = 1;i<=n;++i){for(int j = 1;j<=m;++j){if(!vis[i][j]&&g[i][j]==1){bfs(i,j);}}}std::cout << ans << '\n';
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.3 问题 C: 广搜——营救

我的代码

用char读图,不能用int,后续就是简单的求二维平面的bfs最短路

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e3+5,M = 1e6+5,INF = 0x3f3f3f3f;
int n;
char g[N][N];
bool vis[N][N];
int sx,sy,ex,ey;
using node = std::array<int,3>;
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};void bfs(){std::queue<node> q;node tt;tt[0] = sx,tt[1] = sy,tt[2] = 0;q.emplace(tt);vis[sx][sy] = true;while(!q.empty()){auto t = q.front();q.pop();if(t[0]==ex&&t[1]==ey){std::cout << t[2] << '\n';return;}for(int i = 0;i<4;++i){int u = t[0]+dx[i],v = t[1]+dy[i];if(u<1||u>n||v<1||v>n||vis[u][v]||g[u][v]=='1') continue;vis[u][v] = true;node t1;t1[0] = u,t1[1] = v,t1[2] = t[2]+1;q.emplace(t1);}}
}
void solve(){std::cin >> n;for(int i = 1;i<=n;++i){for(int j = 1;j<=n;++j){std::cin >> g[i][j];}}std::cin >> sx >> sy >> ex >> ey;bfs();
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.4 问题 D: 迷宫的最短路径

我的代码

注意输出不要漏单词或者空格,其他没啥好说的

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e3+5,M = 1e6+5,INF = 0x3f3f3f3f;
int n,m;
char g[N][N];
bool vis[N][N];
int sx,sy,ex,ey;
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
using node = std::array<int,3>;void bfs(){std::queue<node> q;node tt;tt[0] = sx,tt[1] = sy,tt[2] = 0;q.emplace(tt);vis[sx][sy] = true;while(!q.empty()){auto t = q.front();q.pop();if(t[0]==ex&&t[1]==ey){std::cout << "The min steps are:" << t[2] << "!\n";return;}for(int i = 0;i<4;++i){int u = t[0]+dx[i],v = t[1]+dy[i];if(u<1||u>n||v<1||v>m||vis[u][v]||g[u][v]=='#') continue;vis[u][v] = true;node t1;t1[0] = u,t1[1] = v,t1[2] = t[2]+1;q.emplace(t1);}}std::cout << "sorry!\n";
}void solve(){std::cin >> n >> m;for(int i = 1;i<=n;++i){for(int j = 1;j<=m;++j){std::cin >> g[i][j];if(g[i][j]=='S'){sx=i,sy=j;}else if(g[i][j]=='G'){ex=i,ey=j;}}}bfs();
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.5 问题 E: 象棋中的马之进阶

我的代码

求八方向二维平面最短路的bfs

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e3+5,M = 1e6+5,INF = 0x3f3f3f3f;
bool vis[N][N];
int sx,sy,ex,ey;
int dx[] = {-2,-1,1,2,2,1,-1,-2};
int dy[] = {1,2,2,1,-1,-2,-2,-1};
using node = std::array<int,3>;void bfs(){std::queue<node> q;node tt;tt[0] = sx,tt[1] = sy,tt[2] = 0;q.emplace(tt);vis[sx][sy] = true;while(!q.empty()){auto t = q.front();q.pop();if(t[0]==ex&&t[1]==ey){std::cout << t[2] << '\n';return;}for(int i = 0;i<8;++i){int u = t[0]+dx[i],v = t[1]+dy[i];if(u<1||u>9||v<1||v>10||vis[u][v]) continue;vis[u][v] = true;node t1;t1[0] = u,t1[1] = v,t1[2] = t[2]+1;q.emplace(t1);}}std::cout << 0 << '\n';
}
void solve(){std::cin >> sx >> sy >> ex >> ey;bfs();
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.6 问题 F: 搜索——我的世界

我的代码

求三维空间最短路的bfs

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e2+5,M = 1e6+5,INF = 0x3f3f3f3f;int k,n,m;
char g[N][N][N];
bool vis[N][N][N];
int dx[] = {0,0,-1,1,0,0};
int dy[] = {-1,1,0,0,0,0};
int dz[] = {0,0,0,0,1,-1};
using node = std::array<int,4>;
int sx,sy,sz,ex,ey,ez;
void bfs(){std::queue<node> q;node tt;tt[0] = sz,tt[1] = sx,tt[2] = sy,tt[3] = 0;q.emplace(tt);vis[sx][sy][sz] = true;while(!q.empty()){auto t = q.front();q.pop();if(t[0]==ez&&t[1]==ex&&t[2]==ey){std::cout << t[3] << '\n';return;}for(int i = 0;i<6;++i){int u = t[0]+dz[i],v = t[1]+dx[i],w = t[2]+dy[i];if(u<1||u>k||v<1||v>n||w<1||w>m||vis[u][v][w]||g[u][v][w]=='^') continue;vis[u][v][w] = true;node t1;t1[0] = u,t1[1] = v,t1[2] = w,t1[3] = t[3]+1;q.emplace(t1);}}std::cout << 2333333 << '\n';
}
void solve(){std::cin >> k >> n >> m;for(int i = 1;i<=k;++i){for(int j = 1;j<=n;++j){for(int l = 1;l<=m;++l){std::cin >> g[i][j][l];if(g[i][j][l]=='S'){sx=j,sy=l,sz=i;}else if(g[i][j][l]=='E'){ex=j,ey=l,ez=i;}}}}bfs();
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.7 问题 G: 最小倍数

我的代码

不会爆long long,思路见代码

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;
i64 n;void bfs(){std::queue<i64> q;q.emplace(1);while(!q.empty()){auto t = q.front();q.pop();if(t%n==0){std::cout << t << '\n';return;}q.emplace(t*10);q.emplace(t*10+1);}
}
void solve(){while(std::cin >> n){if(n==0) break;bfs();}
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.8 问题 H: 01组成的N的倍数

我的代码

会爆long long和unsigned long long,而且用高精度也会超时,时间复杂度卡得有点死,只能用string

#include <bits/stdc++.h> 
using namespace std;
using i64 = long long;
constexpr int N=1e6+5;
struct node{string str;i64 sum;
} now,temp;
queue<node> q;
int vis[N];
int n;
void bfs(){queue<node> q;memset(vis,0,sizeof(vis));now.str="1";now.sum=1%n;vis[now.sum]=1;q.push(now);while(!q.empty()){now=q.front();q.pop();if(now.sum==0){cout << now.str << endl;break;}temp.str=now.str+'0';temp.sum=(now.sum*10)%n;if(vis[temp.sum]==0){vis[temp.sum]=1;q.push(temp);}temp.str=now.str+'1';temp.sum=(now.sum*10+1)%n;if(vis[temp.sum]==0){vis[temp.sum]=1;q.push(temp);}}
}
int main(){while(~scanf("%d",&n)){bfs();}return 0;
}

3.9 问题 I: 新迷宫探险

我的代码

注意多组数据,写法跟前面的求二维平面最短路的bfs一样

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e2+5,M = 1e6+5,INF = 0x3f3f3f3f;
int n;
char g[N][N];
bool vis[N][N];
int sx,sy,ex,ey;
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
using node = std::array<int,3>;
void bfs(){std::queue<node> q;node tt;tt[0] = sx,tt[1] = sy,tt[2] = 0;vis[sx][sy] = true;q.emplace(tt);while(!q.empty()){auto t = q.front();q.pop();if(t[0]==ex&&t[1]==ey){std::cout << t[2] << '\n';return;}for(int i = 0;i<4;++i){int u = t[0]+dx[i],v = t[1]+dy[i];if(u<1||u>n||v<1||v>n||vis[u][v]||g[u][v]=='#') continue;vis[u][v] = true;node t1;t1[0] = u,t1[1] = v,t1[2] = t[2]+1;q.emplace(t1);}}std::cout << -1 << '\n';
}
void solve(){while(std::cin >> n){for(int i = 1;i<=n;++i){for(int j = 1;j<=n;++j){std::cin >> g[i][j];}}memset(vis,false,sizeof vis);sx = 1,sy = 1,ex = n,ey = n;bfs();}
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.10 问题 J: 山峰和山谷

我的代码

枚举每个没有访问过的点,bfs看是否能够形成山峰或者山谷

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e3+5,M = 1e6+5,INF = 0x3f3f3f3f;
int n;
int g[N][N];
bool vis[N][N];
int ans1,ans2;
int dx[] = {0,0,-1,1,-1,1,1,-1};
int dy[] = {-1,1,0,0,1,1,-1,-1};using node = std::array<int,2>;void bfs(int i,int j){std::queue<node> q;node tt;tt[0] = i,tt[1] = j;q.emplace(tt);vis[i][j] = true;bool flag1 = false,flag2 = false;int cnt = 1;while(!q.empty()){auto t = q.front();q.pop();for(int i = 0;i<8;++i){int u = t[0]+dx[i],v = t[1]+dy[i];if(u<1||u>n||v<1||v>n||(vis[u][v]&&g[u][v]==g[t[0]][t[1]])) continue;if(g[u][v]<g[t[0]][t[1]]) flag1=true;else if(g[u][v]>g[t[0]][t[1]]) flag2=true;else{++cnt;vis[u][v] = true;node t1;t1[0] = u,t1[1] = v;q.emplace(t1);}}}if(flag1&&flag2) return;if(flag1) ++ans1;else if(flag2) ++ans2;if(cnt==n*n) ++ans1,++ans2;
}
void solve(){std::cin >> n;for(int i = 1;i<=n;++i){for(int j = 1;j<=n;++j){std::cin >> g[i][j];}}for(int i = 1;i<=n;++i){for(int j = 1;j<=n;++j){if(!vis[i][j]){bfs(i,j);}}}std::cout << ans1 << ' ' << ans2 << '\n';
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.11 问题 K: 兔兔之漂亮图

我的代码

这题看代码吧,暂时不知道要怎么说清楚这个思路

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 3e5+5,M = 1e6+5,INF = 0x3f3f3f3f;
constexpr int P = 998244353;i64 power(i64 a, i64 b) {i64 res = 1;for (; b; b /= 2, a = a*a%P) {if (b % 2) {res = res*a%P;}}return res;
}std::vector<std::vector<int>> edges(N,std::vector<int>());
std::vector<int> a(N,0);
int n,m;
i64 ans;
std::queue<int> q;
i64 t = 2;void bfs(){for(int i = 1;i<=n;++i){if(a[i]!=0) continue;a[i] = 1;i64 cnt1 = 1,cnt2 = 0;q.emplace(i);while(!q.empty()){auto u = q.front();q.pop();for(auto v:edges[u]){if(a[v]==0){a[v] = 3-a[u];if(a[v]==1) cnt1+=1;else cnt2+=1;q.emplace(v);}else if(a[u]+a[v]!=3){ans = 0;break;}}}if(ans==0) break;//power(2,cnt)ans=ans*((power(t,cnt1)%P+power(t,cnt2)%P)%P)%P;}}
void solve(){std::cin >> n >> m;for(int i = 1;i<=n;++i){edges[i].clear();a[i] = 0;}ans = 1;while(m--){int u,v;std::cin >> u >> v;edges[u].emplace_back(v);edges[v].emplace_back(u);}bfs();std::cout << ans << '\n';
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.12 问题 L: 兔兔的导航系统

我的代码

原题:

2024算法基础公选课练习三(DFS1)的L题

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 2e5+5,M = 1e6+5,INF = 0x3f3f3f3f;int n,m,k;
std::vector<std::vector<int>> edges(N,std::vector<int>());
std::vector<std::vector<int>> reverse_edges(N,std::vector<int>());
std::vector<bool> vis(N,false);
std::vector<int> dist(N,INF);
std::vector<int> p(N,0);
int st,ed;
int maxn=0,minn=0;
void bfs() {std::queue<int> q;vis[st] = true;dist[st] = 0;q.emplace(st);while(!q.empty()) {auto t = q.front();q.pop();for(int i = 0;i<reverse_edges[t].size();++i) {int to = reverse_edges[t][i];if(vis[to]) continue;vis[to] = true;dist[to] = dist[t]+1;q.emplace(to);}}
}void solve(){std::cin >> n >> m;while(m--){int u,v;std::cin >> u >> v;edges[u].emplace_back(v);reverse_edges[v].emplace_back(u);}std::cin >> k;for(int i = 1;i<=k;++i) std::cin >> p[i];st = p[1],ed = p[k];bfs();for(int i = 1;i<=k-1;++i) {int u = p[i],v = p[i+1];bool flag = false;//用于判断是否当前u->v是最短路for(int j = 0;j<edges[u].size();++j) {int w = edges[u][j];if(dist[w]==dist[u]-1) {if(v==w) {flag = true;}else {++maxn;}}}if(!flag) ++minn,++maxn;}std::cout << minn << ' ' << maxn << '\n';
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

3.13 问题 M: 龙哥的换根树

我的代码

bfs两次,然后换根dp

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 2e5+5,M = 1e6+5,INF = 0x3f3f3f3f;
i64 n,k,c;
void bfs(int root,std::vector<std::vector<int>> &edges,std::vector<bool> &vis,std::vector<i64> &dist){std::queue<int> q;vis[root] = true;q.emplace(root);dist[root] = 0;while(!q.empty()){auto u = q.front();q.pop();for(auto &v:edges[u]){if(vis[v]) continue;vis[v] = true;dist[v] = dist[u]+1;q.emplace(v);}}
}
void solve(){std::cin >> n >> k >> c;std::vector<std::vector<int>> edges(n+5,std::vector<int>());std::vector<bool> vis(n+5,false);std::vector<i64> dist(n+5,INF);//vector建边for(int i = 1;i<=n-1;++i){int u,v;std::cin >> u >> v;edges[u].emplace_back(v);edges[v].emplace_back(u);}i64 ans=0,max=0,tmp=0,leaf=1;bfs(1,edges,vis,dist);//拷贝dist数组留用std::vector<i64> prev_dist(n+5);std::copy(dist.begin(),dist.end(),prev_dist.begin());//找到最远的叶子结点leaf和这个最远距离maxfor(int i = 1;i<=n;++i){if(dist[i]>max){max = dist[i];leaf = i;}}//初始化for(int i = 1;i<=n;++i){vis[i] = false;dist[i] = INF;}//以这个叶子结点为根进行bfsbfs(leaf,edges,vis,dist);//枚举换根到每个点最大价值for(int i = 1;i<=n;++i){ans = std::max(ans,dist[i]*k-prev_dist[i]*c);}std::cout << ans << '\n';
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;std::cin >> t;for(int ti = 0;ti<t;++ti) {solve();}return 0;
}

http://www.ppmy.cn/embedded/141200.html

相关文章

网络安全审计机制与实现技术

目录 网络安全审计机制与实现技术网络安全审计机制与实现技术网络审计数据安全分析技术审计日志报表网络审计数据存储技术审计日志存储网络审计数据保护技术 网络安全审计机制与实现技术 技术分类&#xff1a;基于主机的审计机制、基于网络通信的审计机制、基于应用的审计机制…

利用Python爬虫获取商品评论:技术与实践

在当今这个信息爆炸的时代&#xff0c;互联网上充斥着海量的数据。对于电商平台来说&#xff0c;用户评论是了解消费者喜好、优化产品策略的重要依据。Python作为一种强大的编程语言&#xff0c;其丰富的库支持使得爬虫技术成为获取这些数据的有效手段。本文将详细介绍如何使用…

StarRocks-join优化

1、背景 有两个大表&#xff0c;都是6kw级别上下的&#xff0c;通过SR然后包装了一个接口对外提供查询&#xff0c;当前的问题是&#xff0c;这样大的join查询会导致BE直接宕机。并且这个sql很有代表性&#xff0c;我截图如下&#xff1a; 这个表是个单分区&#xff0c;所以直接…

【Zookeeper】四,Zookeeper节点类型、通知、仲裁、会话

文章目录 Zookeeper的架构znode的版本Zookeeper的节点类型层级树状结构znode的不同类型 Zookeeper监视与通知通知的类型 Zookeeper的仲裁Zk的会话会话的生命周期 Zookeeper的架构 Zookeeper的服务器端运行两种模式&#xff1a;独立模式&#xff08;standalone&#xff09;和仲…

Kadb中的ecpg编程

Kadb中的ecpg编程 测试程序&#xff1a; #include "stdio.h" #include "stdlib.h" #include "string.h" // 相当于高级程序语言的全局变量定义 EXEC SQL BEGIN DECLARE SECTION; // 主变量声明开始 const char* target1 "postgres192.168…

HarmonyOS:应用沙箱

一、应用文件概述 应用文件&#xff1a;文件所有者为应用&#xff0c;包括应用安装文件、应用资源文件、应用缓存文件等。 设备上应用所使用及存储的数据&#xff0c;以文件、键值对、数据库等形式保存在一个应用专属的目录内。该专属目录我们称为“应用文件目录”&#xff0c;…

python爬虫安装教程

Python爬虫是用于从网站上自动抓取信息的程序。在开始之前&#xff0c;请确保您了解并遵守目标网站的服务条款&#xff0c;尊重版权法&#xff0c;并且在合理合法的范围内使用爬虫技术。 安装环境 安装Python&#xff1a;首先确保您的计算机上已经安装了Python。推荐版本为3.…

学习日志 --A5rZ

24.11.27 0001:2024 强网杯青少年专项赛 EnterGam 复现已完成 0002:在x86上模拟arm64(搁置,原因:资料过少,可行性过低) 0003:2024 强网杯青少年专项赛 Flip_over 复现终止(无arm真机) 0004: 开始复现 2024 强网杯青少年专项赛 journey_story