2024算法基础公选课练习五(DFS2)

news/2024/12/5 1:23:20/

一、前言

因为此次题目较多,我也不想分成两篇博客来发,我就直接给代码了,如果题目有需要强调的地方再特殊说明

二、题目总览

三、具体题目

3.1 问题 A: 勘探油田

我的代码

8方向的flood fill模型

#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 1e2+5,M = 1e6+5,INF = 0x3f3f3f3f;
int ans;
struct Node{int _x,_y;
};
int n,m;
int dx[] = {0,1,1,1,0,-1,-1,-1};
int dy[] = {1,1,0,-1,-1,-1,0,1};
std::vector<std::vector<char>> g(N,std::vector<char>(N));
std::vector<std::vector<bool>> vis(N,std::vector<bool>(N,false));
void bfs(int x,int y){std::queue<Node> q;Node t;t._x = x,t._y = y;q.emplace(t);vis[x][y] = true;++ans;while(!q.empty()){auto t = q.front();q.pop();for(int i = 0;i<8;++i){int u = t._x+dx[i],v = t._y+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._x = u,t1._y = v;q.emplace(t1);}}
}
void solve(){while(std::cin >> n >> m){if(n==0&&m==0) break;vis.assign(N,std::vector<bool>(N,false));for(int i = 1;i<=n;++i){for(int j = 1;j<=m;++j){std::cin >> g[i][j];}}ans = 0;for(int i = 1;i<=n;++i){for(int j = 1;j<=m;++j){if(g[i][j]=='@'&&!vis[i][j]){bfs(i,j);}}}std::cout << ans << '\n';}
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;
//	std::cin >> t;while(t--){solve();}return 0;
}

3.2 问题 B: 景区旅游

我的代码

一次dfs即可

#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 15,INF = 0x3f3f3f3f;
int n,m;
std::vector<std::vector<char>> g(N,std::vector<char>(N));
std::vector<std::vector<bool>> vis(N,std::vector<bool>(N,false));
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int ans1 = 0,ans2 = INF;
struct node{int _x,_y,_s;
}t,t1;
int sx,sy,ex,ey;
std::queue<node> q; void dfs(int u,int x,int y){if(x==ex&&y==ey){ans1 = std::max(ans1,u);ans2 = std::min(ans2,u);return;}for(int i = 0;i<4;++i){int x1 = x+dx[i],y1 = y+dy[i];if(x1<1||x1>n||y1<1||y1>m||vis[x1][y1]||g[x1][y1]=='0') continue;vis[x1][y1] = true;dfs(u+1,x1,y1);vis[x1][y1] = false;}
}int main(){std::cin.tie(nullptr)->sync_with_stdio(false);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]=='E'){ex=i,ey=j;}}}vis[sx][sy] = true;dfs(0,sx,sy);std::cout << ans1 << ' ' << ans2 << '\n';return 0;
}

3.3 问题 C: 搜索与回溯——迷宫问题

我的代码

#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 15,M = 1e6+5,INF = 0x3f3f3f3f;
int g[N][N];
bool vis[N][N];
int dx[] = {0,1,1,1,0,-1,-1,-1};
int dy[] = {1,1,0,-1,-1,-1,0,1};
int n;
int sx,sy,ex,ey,ans;
void dfs(int x,int y){if(x==ex&&y==ey){++ans;return;}for(int i = 0;i<8;++i){int u = x+dx[i],v = y+dy[i];if(u<1||u>n||v<1||v>n||vis[u][v]||g[u][v]==1) continue;vis[u][v] = true;dfs(u,v);vis[u][v] = false;}
}
void solve(){std::cin >> n;for(int i = 1;i<=n;++i){for(int j = 1;j<=n;++j){std::cin >> g[i][j];}}sx = 1,sy = 1,ex = 1,ey = n;vis[sx][sy] = true;dfs(sx,sy);std::cout << ans << '\n';
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;
//	std::cin >> t;while(t--){solve();}return 0;
}

3.4 问题 D: 搜索——魔法卷轴

我的代码

dfs的时候需要多加一个列是否已经有手印的判断

#include <bits/stdc++.h>
using i64 = long long;
int n,m,res;
char a[15][15];
bool b[15];
void dfs(int k,int s){if(s>=m){res+=1;return;}if(k>n){return;}for(int i=1;i<=n;i++){if(a[k][i] == '@' && b[i]==0){b[i]=1;dfs(k+1,s+1);b[i]=0;}}dfs(k+1,s);
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);std::cin>>n>>m;for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){std::cin>>a[i][j];}}res=0;dfs(1,0);std::cout << res<< '\n';return 0;
}

3.5 问题 E: 搜索与回溯——N 皇后问题

我的代码

经典dfs

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 20;
int n;
char graph[N][N];
bitset<N> col,dg,adg;//column,diagonal,against the diagonal line
void dfs(int dep){if(dep==n){for(int i = 0;i<n;i++){for(int j = 0;j<n;j++){if(graph[i][j]=='Q'){cout << j+1 << " \n"[i==n-1];break;}}}return;}for(int i = 0;i<n;i++){if(!col[i]&&!dg[dep+i]&&!adg[n+i-dep]){col[i]=dg[dep+i]=adg[n+i-dep]=1;graph[dep][i]='Q';dfs(dep+1);col[i]=dg[dep+i]=adg[n+i-dep]=0;graph[dep][i]='.';}}
}
void solve(){cin >> n;for(int i = 0;i<n;i++) for(int j = 0;j<n;j++) graph[i][j]='.';if(n!=3) dfs(0);else{cout << "no solute!\n";}
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T = 1;// cin >> T;while(T--){solve();}return 0;
}

3.6 问题 F: 搜索与回溯——工作分配问题

我的代码

使用next_permutation生成全排列暴力枚举

#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;
int c[25][25];
int n,ans = INF;
void solve(){std::cin >> n;for(int i = 1;i<=n;++i) for(int j = 1;j<=n;++j) std::cin >> c[i][j];std::vector<int> v(n,0);std::iota(v.begin(),v.end(),1);do{int sum = 0;for(int i = 1;i<=n;++i){sum+=c[i][v[i-1]];}ans = std::min(ans,sum);}while(std::next_permutation(v.begin(),v.end()));std::cout << ans << '\n';
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;
//	std::cin >> t;while(t--){solve();}return 0;
}

3.7 问题 G: 观星

我的代码

题目讲得有点模糊,不过分析一下样例应该就能明白

#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 1505,M = 1e6+5,INF = 0x3f3f3f3f;
int n,m;
struct Node{int x,y;
}t,t1;
int dx[] = {0,1,1,1,0,-1,-1,-1};
int dy[] = {1,1,0,-1,-1,-1,0,1};
char g[N][N];
bool vis[N][N];
int cnt=0,maxn=-1;
struct xingzuo{int sx,sy,cnt;
};
std::vector<xingzuo> ans;
void bfs(int sx,int sy){std::queue<Node> q;t.x = sx,t.y = sy;q.emplace(t);vis[sx][sy] = true;int cnt_ = 0;while(!q.empty()){auto t = q.front();q.pop();++cnt_;for(int i = 0;i<8;++i){int u = t.x+dx[i],v = t.y+dy[i];if(u<1||u>n||v<1||v>m||vis[u][v]||g[u][v]=='.') continue;vis[u][v] = true;t1.x = u,t1.y = v;q.emplace(t1);}}xingzuo tmp;tmp.sx = sx,tmp.sy = sy,tmp.cnt = cnt_;ans.emplace_back(tmp);
}
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(g[i][j]=='*'&&!vis[i][j]){++cnt;bfs(i,j);}}}std::set<int> set;std::map<int,int> map;int res = 0;for(const auto &ansi:ans){set.insert(ansi.cnt);map[ansi.cnt]++;}for(const auto &mpi:map){res = std::max(res,mpi.first*mpi.second);}std::cout << set.size() << ' ' << res << '\n';
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;
//	std::cin >> t;while(t--){solve();}return 0;
}

3.8 问题 H: 搜索与回溯——字符序列

我的代码

#include <bits/stdc++.h>
using i64 = long long;
std::vector<char> s(15);
int n,ans;
void dfs(int u) {if(u==n+1) {++ans;return;}for(char c = 'A';c<='C';++c) {s[u] = c;if(u==1||s[u]!=s[u-2]||s[u-1]!=s[u-3]) {dfs(u+1);}else {s[u] = 0;}}
}int main() {std::cin.tie(nullptr)->sync_with_stdio(false);std::cin >> n;dfs(1);std::cout << ans << '\n';return 0;
}

3.9 问题 I: 图的m着色问题(N26)

我的代码

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 1e4+5,M = 1e3+5;
int n,k,m,a[N],b[M][M],ans;
bool check(int s){for(int i=1;i<=s;i++){if(b[i][s]&&a[i]==a[s]){return false;}}return true;
}
void dfs(int s){if(s>n){++ans;return;}for(int i=1;i<=m;i++){a[s]=i;if(check(s)) dfs(s+1);else a[s]=0;}
}
int main(){cin.tie(nullptr)->sync_with_stdio(false);int T = 1;cin >> T;while(T--){memset(b,0,sizeof b);memset(a,0,sizeof a);ans = 0;cin>>n>>k>>m;while(k--){int x,y;cin >> x >> y;b[x][y] = 1;}dfs(1);cout << ans << '\n';}return 0;
}

3.10 问题 J: 搜索与回溯——部落卫队

我的代码

参考了另外一篇博客的写法

#include<cstdio>
#include<cstring>
struct vellager{int other[105],s;
} vec[105];
int m,n,send;
bool can[105],use[105],end[105];
void flag(int x,int tot){if(x>n){if(tot>send){send=tot;memcpy(end,use,n+1);}return;}if(!can[x] && !use[x]){use[x]=true;bool now[105];memcpy(now,can,n+1);for(int j=0;j<vec[x].s;j++) can[vec[x].other[j]]=true;flag(x+1,tot+1);use[x]=false;memcpy(can,now,n+1);}flag(x+1,tot);
}
int main(){scanf("%d%d",&n,&m);for(int i=0;i<m;i++){int x,y;scanf("%d%d",&x,&y);if(!vec[x].other[0]) vec[x].s=0;if(!vec[y].other[0]) vec[y].s=0;vec[x].other[vec[x].s++]=y;vec[y].other[vec[y].s++]=x;}flag(1,0);printf("%d\n",send);for(int i=1;i<=n;i++) i-1?printf(" %d",end[i]):printf("%d",end[i]);return 0;
}

3.11 问题 K: 植物大战僵尸现实版

我的代码

第二次出现这个题了,老师把数据范围改正确了x和y都介于1到1e9之间

思路还是dfs枚举行的状态,然后贪心判断列是否修改,最后答案取max即可

#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;
std::vector<std::vector<i64>> g(15,std::vector<i64>(205,0));
std::vector<std::vector<i64>> tmp(15,std::vector<i64>(205,0));
std::vector<int> v(15,0);
std::vector<i64> pre(205,0);
i64 n,m,x,t;
i64 ans=0;
void dfs(int u){if(u==n+1){i64 cnt = 0;for(int i = 1;i<=n;++i) cnt+=v[i]?1:0;if(cnt>t) return;std::copy(tmp.begin(),tmp.end(),g.begin());pre.assign(205,0);for(int i = 1;i<=n;++i){for(int j = 1;j<=m;++j){g[i][j] = v[i]?x:g[i][j];}}for(int i = 1;i<=m;++i){for(int j = 1;j<=n;++j){pre[i]+=g[j][i];}}i64 sum = 0;std::sort(pre.begin()+1,pre.begin()+1+m);for(int i = 1;i<=m;++i){if(cnt<t&&pre[i]<x*n){sum+=x*n;++cnt;}else{sum+=pre[i];}}ans = std::max(ans,sum);return;}v[u] = 0;dfs(u+1);v[u] = 1;dfs(u+1);
}
void solve(){std::cin >> n >> m >> x >> t;for(int i = 1;i<=n;++i){for(int j = 1;j<=m;++j){std::cin >> g[i][j];}}std::copy(g.begin(),g.end(),tmp.begin());dfs(1);std::cout << ans << '\n';
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;
//	std::cin >> t;while(t--){solve();}return 0;
}

3.12 问题 L: 袜子配对

我的代码

思路同牛客小白月赛105的D题,跳转链接

#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 2e5+5;int n,m,k;
std::vector<int> colors(N,0);struct DSU {int _n;std::vector<int> _fa,_size;DSU(){}DSU(int n){init(n);}void init(int n) {_fa.resize(n);std::iota(_fa.begin(),_fa.end(),0);_size.assign(n,1);}int find(int x) {if(x!=_fa[x]) {_fa[x] = find(_fa[x]);}return _fa[x];}bool same(int x,int y) {return find(x)==find(y);}bool merge(int x,int y) {int fx = find(x);int fy = find(y);if(fx!=fy) {_size[fx]+=_size[fy];_fa[fy] = fx;return true;}return false;}
};
int main() {std::cin.tie(nullptr)->sync_with_stdio(false);std::cin >> n >> m >> k;DSU dsu(N);for(int i = 1;i<=n;++i) {std::cin >> colors[i];}int ans = 0;while(m--) {int l,r;std::cin >> l >> r;if(dsu.merge(colors[l],colors[r])) {++ans;}}std::cout << ans << '\n';return 0;
}

3.13 问题 M: 素数树

我的代码

突然发现自己代码逻辑错了,但是仍然能AC,说明后台测试点的数据不够刁钻,等我修改一下后续再把代码放上来

正确的思路应该是判断该树是否为二叉树,如果是的话,那么只需要对相邻的边依次输出2和3即可;如果不是的话,输出-1然后return处理下一组即可


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

相关文章

平安科技Java面试题及参考答案

多个线程 a++,单个线程不管别的线程怎么改变 a 的值,只管自己的 a 的值,但是只有一个对象 在 Java 中,当多个线程对同一个对象的共享变量 a 进行 a++ 操作时,如果不进行适当的同步处理,就会出现数据不一致的问题。因为 a++ 操作并非原子操作,它实际上包含了读取 a 的值、…

OpenAI:2025年ChatGPT将成为“企业大脑”,并向Agent过渡

刚刚OpenAI 的销售总监在接受《The Information》采访时透露了 ChatGPT 的2025年商业化重点——企业级应用&#xff0c;并设定了一个雄心勃勃的目标&#xff1a;到 2029 年实现年收入 1000 亿美元&#xff01; OpenAI销售总监 Giancarlo "GC" Lionetti 认为企业人工智…

8款Pytest插件助力Python自动化测试

当测试用例变得复杂&#xff0c;或者需要处理大量测试数据时&#xff0c;插件通过使测试更加简洁和结构化而变得非常有用。Python凭借其简洁性和多功能性&#xff0c;成为自动化测试的热门选择&#xff0c;而pytest是最广泛使用的测试框架之一。虽然pytest本身功能强大&#xf…

无人机油气领域应用详解!

一、油气田巡检 自动化巡检&#xff1a;无人机能够搭载高清摄像头、红外热像仪等多种传感器&#xff0c;在高空对油气田进行全方位、无死角的监测。这不仅可以快速发现油气井、管道等设备的表面腐蚀、破损、泄露等安全隐患&#xff0c;还能通过数据分析预测潜在风险区域。 精…

图解人工智能:从规则到深度学习的全景解析

&#x1f31f;作者简介&#xff1a;热爱数据分析&#xff0c;学习Python、Stata、SPSS等统计语言的小高同学~&#x1f34a;个人主页&#xff1a;小高要坚强的博客&#x1f353;当前专栏&#xff1a;Python之机器学习&#x1f34e;本文内容&#xff1a;图解人工智能&#xff1a;…

销售数据分析怎么做?

都知道一份好的销售分析可以帮助企业增加利润&#xff0c;但具体该怎么做出一份优秀的销售数据分析表呢&#xff1f; 很多人一听到要处理数据就已经开始头疼了&#xff0c;也不知道如何进行销售数据分析&#xff0c;这篇给大家分享10 种销售数据分析的技巧和经验&#xff0c;希…

使用Docker Compose安装WordPress(ARM/x86架构)

在本教程中&#xff0c;我们将介绍如何使用Docker Compose安装WordPress&#xff0c;并特别说明ARM和x86架构的区别。 前置条件 Docker已安装&#xff08;确保版本 > 20.10.0&#xff09;Docker Compose已安装&#xff08;V2版本&#xff09;基本的命令行操作知识 架构说…

SpringSecurity6

1.快速入门 2.SpringSecurity底层原理 使用的是委托过滤器,委托过滤器实际上就是 sevlet 过滤器 将自己放入Sevlet环境下 然后里面是一个 过滤器链代理 代理类下又是一个代理过滤器链的集合, 对于不同请求可以有不同的过滤器链, springsecurity有个默认的过滤器链 Defau…