组合型枚举

#include <bits/stdc++.h>
using namespace std;
const int N = 25;
int ans[N];
int n, m;
// last 记录上一次搜索的位置
//  x当前要填充的位置
void dfs(int last, int x) {
	if (x == m + 1) {
		for (int i = 1; i <= m; i++) {
			printf("%d ", ans[i]);
		}
		printf("\n");
	}
	// 可行性剪枝
	// 剩下的数字  n - last 个
	// 已经选择的数字有几个，(x-1)
	if (n - last + (x - 1) < m) return ; // 可行性剪枝
	// 填充当前数字
	for (int i = last + 1; i <= n; i++) {
		ans[x] = i;
		dfs(i, x + 1);
	}
}
int main() {
	cin >> n >> m;
	dfs(0, 1);
	return 0;
}

枚举子集

// 在n 个位置上 填 N 或  Y
// N 和 Y 可以重复填， 不需要标记
#include <bits/stdc++.h>
using namespace std;
const int N  = 15;
char ans[N];
int n;
// 在位置 X 上进行填充
void dfs(int x) {
	// 结束条件
	if (x == n + 1) {
		for (int i = 1; i <= n; i++) {
			cout << ans[i];
		}
		cout << endl;
		return ;
	}
	// 填充
	for (int i = 1; i <= 2; i++) {
		if (i == 1) ans[x] = 'N';
		if (i == 2) ans[x] = 'Y';
		dfs(x + 1); // 填充下一个位置
	}
}
int main() {
	cin >> n;
	dfs(1);
	return 0;
}

枚举排列

// 1. 排列
// 2. n个人里面选择k个
#include <bits/stdc++.h>
using namespace std;
int n, k;
int ans[15]; // 用来存排列
bool vis[15];  // 标记数字有没有被用
void dfs(int x) { // 在当前位置x填充数字
	// 结束条件
	if (x == k + 1) { // 排满了
		for (int i = 1; i <= k; i++)
			cout << ans[i]<<" ";
		cout << endl;
		return ;
	}
	// 当前没填满
	for (int i = 1; i <= n; i++) {
		// 如果当前数字被填充了，跳过
		if (vis[i]) continue;
		// 当前数字没有被填充
		vis[i] = 1;   // 当前数字被填充，跳过
		ans[x] = i;  // 当前位置填充数字i
		dfs(x + 1); // 继续往下填充
		vis[i] = 0; // 当前位置不填充该数字，看有没有其他可能
	}
}
int main() {
	cin >> n >> k;
	dfs(1);
	return 0;
}

能否走通迷宫

#include <bits/stdc++.h>
using namespace std;
const int N = 101;
int n, m;
bool vis[N][N];

// 方向数组
int dx[] = {-1, 1, 0, 0};

int dy[] = {0, 0, -1, 1};
char a[N][N];

bool flg; // 标记是否走到右下角
void dfs(int x, int y) {
	// 结束条件,右下角
	if (x == n && y == m) {
		flg = 1;
		return ;
	}
	// 证明没有走到
	// 从当前点继续搜索
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		// 判断是否越界
		if (nx < 1 || nx > n || ny < 1 || ny > m)
			continue;
		// 判断是否访问过
		if (vis[nx][ny])
			continue;
		// 判断是否能走
		if (a[nx][ny] == '#')
			continue;
		// 当前点能走
		vis[nx][ny] = 1;
		dfs(nx, ny);  // 从当前点继续深搜
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	if (a[1][1] == '#' || a[n][m] == '#') {
		cout << "NO";
		return 0;
	}
	vis[1][1] = 1;
	dfs(1, 1);
	if (flg)
		cout << "YES";
	else
		cout << "NO";
	return 0;
}

输出迷宫路径

#include <bits/stdc++.h>
using namespace std;
const int N = 16;

int dx[] = {0, -1, 0, 1};

int dy[] = {-1, 0, 1, 0};
bool vis[N][N], flg = 1;
int a[N][N], n, m, sx, sy, fx, fy;
pair<int, int > ans[N * N];


void dfs(int x, int y, int cnt) {
	if (x == fx && y == fy) {
		flg = 0; // 已经输出过取消标记
		// 输出路径
		printf("(%d,%d)", ans[1].first, ans[1].second);
		for (int i = 2; i <= cnt; i++)
			printf("->(%d,%d)", ans[i].first, ans[i].second);
		cout << endl;
		return ;
	}
	// 遍历四个方向继续走
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 1 || nx > n || ny < 1 || ny > m)
			continue ;
		if (vis[nx][ny])
			continue ;
		if (a[nx][ny] == 0)
			continue;
		vis[nx][ny] = 1;
		cnt++; // 新走了一个点， cnt++
		// 记录下来当前走的点
		ans[cnt].first = nx;
		ans[cnt].second = ny;
		dfs(nx, ny, cnt);
		vis[nx][ny] = 0;
		cnt--;
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	cin >> sx >> sy >> fx >> fy;
	// 特判起点
	if (a[sx][sy] == 0 || a[fx][fy] == 0) {
		cout << -1;
		return 0;
	}
	vis[sx][sy] = 1;
	ans[1].first = sx;
	ans[1].second = sy;
	dfs(sx, sy, 1);
	if (flg)
		cout << -1;
	return 0;
}

连通块问题/洪水填充问题

// 洪水填充
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int n, m, ans;
char a[N][N];

int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1};

int dy[8] = {1, -1, 0, 0, 1, 1, -1, -1};
bool vis[N][N];

void dfs(int x, int y) {
	// 扩展
	for (int i = 0; i < 8; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 1 || nx > n || ny < 1 || ny > m)
			continue;
		if (vis[nx][ny])
			continue;
		if (a[nx][ny] == '.')
			continue;
		vis[nx][ny] = 1;
		dfs(nx, ny);
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++ ) {
			if (vis[i][j] || a[i][j] == '.')
				continue;
			ans++; // 多了一个水坑
			dfs(i, j);
		}
	cout << ans;
	return 0;
}

星系

// 一个联通快就是一个星座
// 联通块中星星相同一个星系
// 求星系个数 最大星系包含的星星的数量
// 计数数组，cnt[i] = j
// 代表 星星个数为 i 的星座有 j 个
// 第一次cnt[i]=1的时候出现一个新的星系
// ans = max(ans, i *cnt[i])
#include <bits/stdc++.h>
using namespace std;
const int N = 1500;
int n, m, cnt[int(1e5 + 10)];
char a[N][N];
bool vis[N][N];

int tot; // 来记录当前星座有几个星星

void dfs(int x, int y) {
	for (int i = 0; i < 8; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		// 判断越界
		// 判断是否访问过
		// 判断是否能走
		vis[nx][ny] = 1;
		tot++;   // 星星数量增加
		dfs(nx, ny);
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (vis[i][j] || a[i][j] == '.')
				continue;
			// 跑联通块
			tot = 1;
			vis[i][j] = 1;
			dfs(i, j);
			cnt[tot]++;
		}
	}
	int s1 = 0, s2 = 0;
	for (int i = 1; i <= 1e5; i++) {
		if (cnt[i]) {
			s1++; // 星系数量增加
			s2 = max(s2, i * cnt[i]);
		}
	}
	cout << s1 << " " << s2;
	return 0;
}

9011

// 枚举所有空调组合的可能
// 看这个是否能符合奶牛的要求
// 在符合奶牛要求的组合里面选择花费最低的
#include <bits/stdc++.h>
using namespace std;
const int N =  1e3;
int n, M, s[N], t[N], c[N];
int a[N], b[N], p[N], m[N];
int ans = 2146483647;
int tmp[int(1e3)]; // tmp[i] = j ,意味着 i 这个点降低了 j  的温度
bool v[N]; // 记录当前空调是否被选择

// x 代表当前要判断第几个是否选择
// cost 是花费了多少
void dfs(int x) {
	if (x > M) { // 空调已经抉择完毕
		int cost = 0;
		memset(tmp, 0, sizeof(tmp));
		// 判断当前子集是否符合要求
		for (int i = 1; i <= M; i++) {
			if (v[i]) {
				cost += m[i];
				// 修改每一个空调能控制的区间
				for (int j = a[i]; j <= b[i]; j++)
					tmp[j] += p[i]; // 当前点空调温度降低值修改
			}
		}
		// 判断空调温度是否符合要求
		bool flg = 1;
		for (int i = 1; i <= 100; i++) {
			// c[i] 要求的问题， tmp[i] 实际降低下来的温度
			if (c[i] > tmp[i]) {
				flg = 0;
				break;
			}
		}
		if (flg)
			ans = min(ans, cost);
		return ;
	}
	// 如果没有抉择完毕
	dfs(x + 1); // 当前空调没有选择
	v[x] = 1;
	dfs(x + 1);
	v[x] = 0; // 回溯
}

int main() {
	cin >> n >> M;
	for (int i = 1; i <= n; i++) {
		int t1;
		cin >> s[i] >> t[i] >> t1;
		for (int j = s[i]; j <= t[i] ; j++) {
			c[j] = max(c[j], t1);
		}
	}
	for (int i = 1; i <= M; i++)
		cin >> a[i] >> b[i] >> p[i] >> m[i];
	// 枚举子集求最小的花费
	dfs(1);
	cout << ans;
	return 0;
}