当前位置： 首页 > article >正文

DFS刷题

article 2025/3/26 8:09:02

洛谷P2089烤鸡

#include<iostream>
using namespace std;
const int N = 20, M = 1000010;
int ans[N];
int dp[M][N];
int n, count;
void dfs(int x, int sum){
	if(sum > n)return;
	if(x > 10){
		if(sum == n){
			count++;
			for(int i = 1; i <= n; i++)dp[count][i] = ans[i];
		}
		return;
	}
	for(int i = 1; i <= 3; i++){
		ans[x] = i;
		dfs(x + 1, sum + i);
		ans[x] = 0; 
	}
} 
int main(){
	cin >> n;
	dfs(1, 0);
	cout << count << endl;
	for(int i = 1; i <= count; i++){
		for(int j = 1; j <= 10; j++){
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
	
	return 0;
}

洛谷P1088火星人

next_permutation函数

#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
const int N = 10010;
int a[N];

int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++)cin >> a[i];
	if(m == 0){
		for(int i = 1; i <= n; i++)cout << a[i] << " ";
	}
	while(m--){
		next_permutation(a + 1, a + n + 1);
	}
	for(int i = 1; i <= n; i++)cout << a[i] << " "; 
	
	return 0;
}

 DFS

#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
const int N = 10010;
int ans[N], a[N];
bool st[N];
int cnt;
void dfs(int x){
	if(cnt >= m + 1)return;
	if(x > n){
		cnt++;
		if(cnt == m + 1){
			for(int i = 1; i <= n; i++)cout << ans[i] << " ";
		}
		return;
	}
	for(int i = 1; i <= n; i++){
		if(!cnt){
			i = a[x];
		}
		if(!st[i]){
			ans[x] = i;
			st[i] = true;
			dfs(x + 1);
			ans[x] = 0;
			st[i] = false;
		}
	}
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++)cin >> a[i];
	dfs(1);
	
	return 0;
}

洛谷P1149火柴棒

#include<iostream>
#include<algorithm>
using namespace std;
int n;
const int N = 10010;
int dist[N] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int arr[4];
int ans;
void dfs(int x, int sum){
	if(sum > n)return;
	if(x > 3){
		if(arr[1] + arr[2] == arr[3] && sum == n){
			ans++;
		}
		return;
	}
	for(int i = 0; i <= 1000; i++){
		arr[x] = i;
		dfs(x + 1, sum + dist[i]);
		arr[x] = 0;
	}
}
int main(){
	cin >> n;
	n -= 4;
	for(int i = 10; i <= 10000; i++){
		dist[i] = dist[i % 10] + dist[i / 10];
	}
	dfs(1, 0);
	cout << ans << endl;
	
	return 0;
}

洛谷P2036PERKET

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
const int N = 20;
int acid[N], bitter[N];
int ans = 0x7fffffff;
bool st[N];

void dfs(int x){
	if(x > n){
		int sum1 = 1;
		int sum2 = 0;
		bool has_sc = false;
		for(int i = 1; i <= n; i++){
			if(st[i] != 0){
				has_sc = true;
				sum1 *= acid[i];
				sum2 += bitter[i];
			}
			if(has_sc)ans = min(ans, abs(sum1 - sum2));
		}
		return;
	}
	st[x] = true;
	dfs(x + 1);
	st[x] = false; 
	dfs(x + 1); 
}
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++)cin >> acid[i] >> bitter[i];
	dfs(1);
	cout << ans << endl;
	
	return 0;
}

洛谷P1135奇怪的电梯

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n, a, b;
const int N = 210;
int s[N];
int ans = 0x7fffffff;
bool st[N];
void dfs(int x, int cnt){
	if(cnt >= ans)return;
	if(x == b){
		ans = min(ans, cnt);
		return;
	}
	int up = x + s[x];
	if(up <= n && !st[up]){
		st[up] = true;
		dfs(x + s[x], cnt + 1);
		st[up] = false;
	}
	int down = x - s[x];
	if(down >= 1 && !st[down]){
		st[down] = true;
		dfs(x - s[x], cnt + 1);
		st[down] = false; 
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> a >> b;
	for(int i = 1; i <= n; i++)cin >> s[i];
	st[a] = true;
	dfs(a, 0);
	if(ans == 0x7fffffff)cout << -1 << endl;
	else cout << ans << endl;
	return 0;
}

洛谷P1683

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m;
const int N = 25;
char mp[N][N];
bool st[N][N];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int ans = 1;
void dfs(int x, int y){
	
	for(int i = 0; i < 4; i++){
		int a = x + dx[i], b = y + dy[i];
		if(a < 1 || a > n || b < 1 || b > m)continue;
		if(mp[a][b] != '.')continue;
		if(st[a][b])continue;
		st[a][b] = true;
		ans++;
		dfs(a, b);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> m >> n;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> mp[i][j];
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(mp[i][j] == '@'){
				st[i][j] = true;
				dfs(i, j);
			}
		}
	}
	cout << ans << endl;
	
	
	return 0;
}

洛谷P1596

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110;
char g[N][N];
bool st[N][N];
int n, m;
int ans;
int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};
void dfs(int x, int y){
	for(int i = 0; i < 8; i++){
		int a = x + dx[i], b = y + dy[i];
		if(a < 1 || a > n || b < 1 || b > m)continue;
		if(st[a][b] || g[a][b] != 'W')continue;
		st[a][b] = true;
		dfs(a, b);
	}
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> g[i][j];
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(g[i][j] == 'W' && !st[i][j]){
				ans++;
				st[i][j] = true;
				dfs(i, j);
			}
		}
	}
	cout << ans << endl; 
	
	return 0;
}

acwing1114棋盘问题

#include<iostream>
#include<cstring>
using namespace std;
int n, m;
const int N = 10;
char g[N][N];
bool col[N];
int ans;
void dfs(int x, int cnt){
    if(cnt == m){
        ans++;
        return;
    }
    if(x > n)return;
    for(int i = 1; i <= n; i++){
        if(!col[i] && g[x][i] == '#'){
            col[i] = true;
            dfs(x + 1, cnt + 1);
            col[i] = false;
        }
    }
    dfs(x + 1, cnt);
}
int main(){
    while(cin >> n >> m, (n != -1 && m != -1)){
        memset(g, 0, sizeof(g));
        ans = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                cin >> g[i][j];
            }
        }
        memset(col, 0, sizeof(col));
        dfs(1, 0);
        cout << ans << endl;
    }
    
    return 0;
}

洛谷P1025数的划分

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n, k;
const int N = 210;
int ans;
void dfs(int x, int cnt, int start){
	if(x > k){
		if(cnt == 0)ans++;
		return;
	}
	if(x > k || cnt < 0)return;
	for(int i = start; i <= cnt;  i++){
		dfs(x + 1, cnt - i, i);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;
	dfs(1, n, 1);
	cout << ans << endl;
	
	return 0;
}

洛谷P1019单词接龙

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
const int N = 25;
string str[N];
int g[N][N];//g[i][j]表示第i个字符串到j个的共同部分的长度 
int used[100];
int ans;
void dfs(string dragon, int x){
	ans = max(ans, (int)dragon.size());
	used[x]++;
	for(int i = 1; i <= n; i++){
		if(g[x][i] && used[i] < 2){
			dfs(dragon + str[i].substr(g[x][i]), i);
		}
	}
	used[x]--;
}
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++)cin >> str[i];
	char start; cin >> start;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			for(int k = 1; k <= min(str[i].size(), str[j].size()); k++){
				string a = str[i], b = str[j];
				if(a.substr(a.size() - k, k) == b.substr(0, k)){
					g[i][j] = k;
					break;
				}
			}
		}
	}
	for(int i = 1; i <= n; i++){
		if(str[i][0] == start){
			dfs(str[i], i);
		}
	}
	cout << ans << endl;
	
	return 0;
}


http://www.kler.cn/a/596829.html

相关文章：

  • 树莓派5的供电与启动
  • 强大的AI网站推荐（第三集）—— AskO3
  • MyBatis-Plus 的加载及初始化
  • FastAPI WebSocket 无法获取真实 IP 错误记录
  • 蓝桥杯 劲舞团
  • Springboot之RequestAttributes学习笔记
  • 【深度学习入门_机器学习理论】梯度提升决策树（GBDT）
  • 【算法学习之路】13.BFS
  • 【go】如何处理可选配置
  • CSS 中@media查询的工作原理，如何利用它实现不同设备的样式适配
  • 大数据平台上的数据建模与分析：从数据到决策的跃迁
  • 旋转编码器
  • 基于随机森林回归预测葡萄酒质量
  • OpenCV中的矩阵操作
  • OSASIS（One-Shot Structure-Aware Stylized Image Synthesis）
  • 计算机网络性能优化相关内容详解
  • JavaScript基础-API 和 Web API
  • QT笔记----QCheckBox
  • 零、ubuntu20.04 安装 anaconda
  • 100道C#高频经典面试题及答案解析：C#程序员面试题库分类总结