连通性
1112. 迷宫
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
char g[N][N];
int n;
int sx, sy, ex, ey;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
bool st[N][N];
bool dfs(int x, int y) {
if(x == ex && y == ey) {
return true;
}
if(g[x][y] == '#') return false;
st[x][y] = true;
for(int i = 0; i < 4; i++) {
int xx = x + dx[i], yy = y + dy[i];
if(xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
if(st[xx][yy]) continue ;
if(dfs(xx, yy)) return true;
}
return false;
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
memset(st, false, sizeof st);
scanf("%d", &n);
for(int i = 0; i < n; i++) cin >> g[i];
cin >> sx >> sy >> ex >> ey;
if(g[sx][sy] == '#' || g[ex][ey] == '#') puts("NO");
else if(dfs(sx, sy))
puts("YES");
else
puts("NO");
}
return 0;
}
搜索顺序
- 需要恢复现场的原因:联想二叉搜索树,保证当前节点对于每一个儿子节点的状态都是相同的
指数型枚举: 无个数限制
- 题目描述: 从 1~n 这 n 个整数中随机选取任意多个,输出所有可能的选择方案。
- 朴素dfs枚举
int n;
vector<int> ans;
void calc(int x) {
if(x == n + 1) {
for(auto c: ans) printf("%d ", c);
puts("");
return ;
}
calc(x + 1);
ans.push_back(x);
calc(x + 1);
ans.pop_back(); // 恢复原始状况
}
void solve() {
scanf("%d", &n);
calc(1);
}
- 二进制压缩版dfs
int n;
void dfs(int u, int state) { // state 的二进制表示中,选过的数所对应的二进制位为1
if(u == n) { // 从零开始到n - 1结束
for(int i = 0; i < n; i++) {
if(state >> i & 1) printf("%d ", i + 1); // state的二进制表示中为一的表示选中,输出
}
printf("
");
return ;
}
dfs(u + 1, state); // 不选
dfs(u + 1, state | 1 << u); // 选, 并将其置为一
}
void solve() {
scanf("%d", &n);
dfs(0, 0);
}
组合型枚举:有个数限制
- 题目描述: 从 1~n 这 n 个整数中随机选出 m 个,输出所有可能的选择方案。
- 朴素dfs: 运行时间过长
vector<int> ch;
int a, b;
void calc(int x) {
if(x > a + 1) return ;
if(ch.size() == b) {
for(int i = 0; i < ch.size(); i++) printf("%d ", ch[i]);
printf("
");
return ;
}
ch.push_back(x);
calc(x + 1);
ch.pop_back();
calc(x + 1);
}
void solve() {
scanf("%d%d", &a, &b);
calc(1);
return 0;
}
- 二进制压缩版dfs
int a, b;
void dfs(int u, int state, int s) {
if(s + a - u < b) return ; // 当前加上剩下的所有的也不满足条件
if(s == b) {
for(int i = 0; i < a; i++) {
if(state >> i & 1) printf("%d ", i + 1);
}
printf("
");
return;
}
dfs(u + 1, state | 1 << u, s + 1); // 选
dfs(u + 1, state, s); // 不选
}
void solve() {
scanf("%d%d", &a, &b);
dfs(0, 0, 0);
}
排列型枚举: 排列数
- 题目描述:把 1~n 这 n 个整数排成一行后随机打乱顺序,输出所有可能的次序。
- 朴素版
- 建立一个布尔数组判断数是否被选过
const int N = 10;
vector<int> ch;
bool st[N];
int n;
void dfs(int u) {
if(u == n + 1) {
for(int i = 0; i < n; i++) printf("%d ", ch[i]);
printf("
");
return ;
}
for(int i = 1; i <= n; i++) {
if(!st[i]) {
ch.push_back(i);
st[i] = true;
dfs(u + 1);
st[i] = false; // 恢复现场
ch.pop_back(); // 恢复现场
}
}
}
void solve() {
scanf("%d", &n);
dfs(1);
return 0;
}
- 二进制压缩版dfs
- 使用一个32位整型变量,使用其二进制表示数是否被使用, 为1的位表示已经使用
const int N = 10;
vector<int> ch;
int n;
void dfs(int u, int state) {
if(ch.size() == n) {
for(int i = 0; i < n; i++) printf("%d ", ch[i]);
printf("
");
return ;
}
for(int i = 1; i <= n; i++) {
if(!((state >> i) & 1)) {
ch.push_back(i);
dfs(u + 1, state | 1 << i); // 选择该数,置为1
ch.pop_back(); // 恢复现场
}
}
}
void solve() {
scanf("%d", &n);
dfs(1, 1);
return 0;
}
剪枝
165. 小猫爬山
- 加入把重量大的猫放入缆车,那么该状态的子树的分支将会是比较少的,因此采用这种策略进行DFS
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int w[20], sm[20];
int ans = 20;
int n, W;
void dfs(int u, int k) {
// 最优化剪枝
if(k >= ans) return ;
if(u == n) {
ans = k;
return ;
}
for(int i = 0; i < k; i++) {
// 可行性剪枝
if(sm[i] + w[u] <= W) {
sm[i] += w[u];
dfs(u + 1, k);
sm[i] -= w[u];
}
}
sm[k] = w[u];
dfs(u + 1, k + 1);
sm[k] = 0;
}
int main() {
scanf("%d%d", &n, &W);
for(int i = 0; i < n; i++) scanf("%d", &w[i]);
sort(w, w + n);
reverse(w, w + n);
dfs(0, 0);
cout << ans;
return 0;
}
166. 数独
#include <iostream>
using namespace std;
const int N = 9, M = 1 << N;
int mp[M], ones[M];
int col[N], row[N], cell[3][3];
char str[100];
void init() {
for(int i = 0; i < N; i++)
col[i] = row[i] = (1 << N) - 1;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
cell[i][j] = (1 << N) - 1;
}
void draw(int x, int y, int t, bool st) {
if(st) str[x * N + y] = '1' + t;
else str[x * N + y] = '.';
int v = 1 << t;
if(!st) v = -v;
row[x] -= v;
col[y] -= v;
cell[x / 3][y / 3] -= v;
}
// 返回最后一个1
int lowbit(int x) {
return x & -x;
}
int get(int x, int y) {
return row[x] & col[y] & cell[x / 3][y / 3];
}
bool dfs(int cnt) {
if(!cnt) return true;
int minv = 10;
int x, y;
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
if(str[i * N + j] == '.') {
int state = get(i, j);
if(ones[state] < minv) {
minv = ones[state];
x = i, y = j;
}
}
// cout << x << ' ' << y << endl;
int state = get(x, y);
for(int i = state; i; i -= lowbit(i)) {
int t = mp[lowbit(i)];
draw(x, y, t, true);
if(dfs(cnt - 1)) return true;
draw(x, y, t, false);
}
return false;
}
int main() {
for(int i = 0; i < 1 << N; i++)
for(int j = 0; j < N; j++)
ones[i] += i >> j & 1;
for(int i = 0; i < N; i++) mp[1 << i] = i;
while(cin >> str, str[0] != 'e') {
init();
int cnt = 0;
for(int i = 0, k = 0; i < N; i++)
for(int j = 0; j < N; j++, k++)
if(str[k] != '.') {
int t = str[k] - '1';
draw(i, j, t, true);
} else
cnt++;
dfs(cnt);
puts(str);
}
return 0;
}
167. 木棒
- 剪枝1:所有木棍的长度之和必须是组数的倍数
- 剪枝2:从大到小枚举木棒
- 剪枝3:按照组合数方式枚举
- 剪枝4:如果当前木棒不能加到其中,那么可以直接略过后面所有与此木棒长度相等的木棒
- 剪枝5:如果是木棒的第一根失败,那么接下来的一定失败
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 70;
int a[N], n, tot, length;
int ans;
bool st[N]; // 剪枝3
// 当前枚举的大棍数量,当前长度,开始位置
bool dfs(int u, int s, int start) {
if(u * length == tot) return true;
if(s == length) return dfs(u + 1, 0, 0);
for(int i = start; i < n; i++) {
if(st[i] || s + a[i] > length) continue;
st[i] = true;
if(dfs(u, s + a[i], i + 1)) return true;
st[i] = false;
// 剪枝5、1
if(!s || s + a[i] == length) return false;
// 剪枝4
int j = i;
while(j < n && a[i] == a[j]) j++;
i = j - 1;
}
return false;
}
int main() {
while(cin >> n, n) {
tot = 0;
memset(st, false, sizeof st);
for(int i = 0; i < n; i++) {
scanf("%d", &a[i]);
tot += a[i];
}
// 剪枝2
sort(a, a + n); reverse(a, a + n);
length = 1;
while(true) {
if(tot % length == 0 && dfs(0, 0, 0)) {
cout << length << endl;
break;
}
else length++;
}
}
return 0;
}
168. 生日蛋糕
-
剪枝1:从底向上搜索,从大到小枚举(r、h)
-
剪枝2:当前第(u)层,每层半径高度均严格递增
- (R_u leq min(R_{u + 1} - 1, sqrt{N - V}))
- (R_u leq R_{u + 1} - 1)
- (u)层之下的总体积为(V), 总体积为(N), 从(u)层之上的总体积为:(N - V = pi R^2H),题目不用考虑(pi), (H) 最小取(1), 因此(R_u leq sqrt{N - V})
- (H_u leq min(H_{u + 1}, frac{N - V}{R^2}))
- (R_u leq min(R_{u + 1} - 1, sqrt{N - V}))
-
剪枝3:预处理前(u)层体积最小值(minv)、表面积最小值(mins),以保证:
- (V + minv_u leq N)
- (S + mins_u < S)
-
剪枝4:(s + frac{2(N - V)}{R_(u + 1)} + 1 geq ans), break;
- (S_u = sum_{k = 1}^u2 pi R_kH_k)
- (N - V = sum_{k = 1}^upi R_k^2H_k)
- 忽略(pi): (S_u = frac{2}{R_u + 1}sum_{k = 1}^u R_kHR_{u + 1} > frac{2}{R_u + 1}sum_{k = 1}^upi R_k^2H_k)
- 即(S_{u} + s geq frac{2(N - V)}{R_(u + 1)})
迭代加深
170. 加成序列
- 题目特点:对于有些分支可能搜索深度很深,但最终答案只在深度很浅的分支当中
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int n, path[N];
bool dfs(int u, int depth) {
if(u > depth) return false;
if(path[u - 1] == n) return true;
bool st[N] = {false};
for(int i = u - 1; i >= 0; i--)
for(int j = i; j >= 0; j--) {
int s = path[i] + path[j];
if(s > n || s <= path[u - 1] || st[s]) continue;
st[s] = true;
path[u] = s;
if(dfs(u + 1, depth)) return true;
}
return false;
}
int main() {
path[0] = 1;
while(cin >> n, n) {
int depth = 1;
while(!dfs(1, depth)) depth ++;
for(int i = 0; i < depth; i++)
cout << path[i] << " ";
cout << endl;
}
return 0;
}