2024算法基础公选课练习七（BFS1）

一、前言

还是偏基础的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;using vvi = std::vector<std::vector<int>>;
using vi = std::vector<int>;
using vb = std::vector<bool>;
#define eb emplace_backint n,m,k;
vvi edges(N,vi());//如果edges[u][idx]=v，那么表示对于节点u，第idx边为u->v
vvi reverse_edges(N,vi());//同上，但是这次的边是反向存储的即v<-u
vb vis(N,false);
vi dist(N,INF);//距离数组（指到当前节点到ed节点的最短路）vi p(N,0);int st,ed;int ans1,ans2;void bfs(){std::queue<int> q;q.emplace(ed);//从终点反向求最短路vis[ed] = true;dist[ed] = 0;//终点到终点距离为0while(!q.empty()){auto u = q.front();q.pop();for(auto &v:reverse_edges[u]){if(vis[v]) continue;vis[v] = true;dist[v] = dist[u]+1;//计算v到终点的最短路q.emplace(v);}}
}void solve(){std::cin >> n >> m;while(m--){int u,v;std::cin >> u >> v;edges[u].eb(v);reverse_edges[v].eb(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){//枚举k-1个实际路径int u = p[i],v = p[i+1];//实际路径为u->vif(dist[u]==dist[v]+1){//当前u->v是最短路for(auto &w:edges[u]){//枚举所有u->w的路径if(dist[w]==dist[v]&&w!=v){//如果不止有一条最短路++ans2;//那么最多重构次数可以+1，因为可以选择另外一条最短路走break;}}}else{//当前u->v不是最短路++ans1;//那么必须重构，最少和最多重构次数都+1++ans2;}}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.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;
}