2024算法基础公选课练习五（DFS2）

一、前言

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

二、题目总览

三、具体题目

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;
}