当前位置 博文首页 > Keven_11的博客：C++ 火柴棒问题 (深度优先搜索+剪枝)
有一个由火柴棒作为边组成的N×N 的格子。(N≤5)按照下图，给火柴棒编号。（这是 N=3 的情况,其它情况类似）
http://style.iis7.com/uploads/2021/08/11160045296.png 这是此图链接
现在将移除某些火柴棒的状态作为初始状态，需要再移除一些火柴棒，以保证图中一个正方形也没有。请求出所有需要移除火柴棒的最少根数。
输入格式
第一行一个整数 T 表示测试数据个数。
对于每个测试数据，第一行整数 NN ，表示正方形的边长。第二行以一个整数 m 开头（m≤2n(n+1)），接下来 m 个不相同的整数，范围在 [1,2n(n+1)] 之间，以空格分开。
输出格式
对每个测试数据，输出一个整数表示最少需要移除的火柴棒个数。
输出时每行末尾的多余空格，不影响答案正确性
要求使用「文件输入输出」的方式解题，输入文件为 matchstick.in，输出文件为 matchstick.out
样例输入
2
2
0
3
3 12 17 23
样例输出
3
3
题解见下，（有注释），此题用深度优先搜索+剪枝，代码比较的复杂，但我保证我的代码时间复杂度很低：
/*
如果移除当前火柴棒后，不能破坏任何正方形，那就没必要移除.cpp
如果把剩下的火柴棒全部移除，也会留下某些正方形，那后面情况就不用考虑了.cpp
*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<utility>
using namespace std;
typedef long long ll;
const int N=90;
vector<int>d[N];
bool belong[N][N]; // belong[i][j] 表示火柴棒 i 是否属于正方形 j.cpp
int mmax[N]; // mmax[i] 表示正方形 i 最大编号的火柴棒.cpp
int m,ct; // m 为总的火柴棒数量，ct 为初始正方形数量.cpp
int ans; // 最终答案.cpp
bool vis[N]; // 火柴棒初始状态 true 表示不存在.cpp
// u为当前火柴棒的编号，sum为当前移除的火柴棒数量，state为当前完整正方形的集合.cpp
int hstar(int u, ll state) {
vector<pair<int, int> > ps;
for (int i = 0; i < ct; i++) {
if (state>>i&1) {
int num = 0; // 火柴棒数量
for (int k=0;k<d[i].size();k++){
int x=d[i][k];
if (x >= u) {
num++;
}
}
ps.push_back(make_pair(num,i));
}
}
sort(ps.begin(), ps.end());
int res = 0;
vector<bool> used(m, false); // 已选集合中是否含有这根火柴棒
for (int i = 0; i < ps.size(); i++) {
int id = ps[i].second; // 正方形编号
bool ok = true;
for (int k=0;k<d[id].size();k++) {
int x=d[id][k];
if (used[x]) {
ok = false;
break;
}
}
if (ok) {
res++;
for (int k=0;k<d[id].size();k++) {
int x=d[id][k];
used[x] = true;
}
}
}
return res;
}
void dfs(int u,int sum,ll state){
if (sum + hstar(u,state)>= ans) {
return;
}
if (u==m+1){
if (state==0){
ans=min(ans,sum);
}
return;
}
// 初始火柴棒不存在，直接搜下一个.cpp
if (vis[u]){
dfs(u+1,sum,state);
return;
}
int flag=0; // 0 不用移除 1 可以移除 2 必须移除.cpp
for (ll i=0;i<ct;i++){
if ((state & (1<<i)) && belong[u][i]){
if (mmax[i]==u){
flag=2;
}else if (flag==0){
flag=1;
}
}
}if (flag==0){
dfs(u+1,sum,state);
}else if (flag==2){
for (int i=0;i<ct;i++){
if ((state>>i&1) && belong[u][i]){
state^=1LL<<i;
/*^ 是把两个数写成二进制的样子，对每一位而言，相同的话结果就是 0，不同结果就是 1这里 state ^= 1LL << i; 相当于把 state 的第 i 位，0 变 1 或者 1 变 0，这里它肯定是 1 变 0,>> 是右移，相当于是去掉二进制最后多少位，state >> i & 1，就是看第 i 位是不是 1*/
}
}
dfs(u+1,sum+1,state);
}else{
dfs(u+1,sum,state);
for (int i=0;i<ct;i++){
if ((state>>i&1) && belong[u][i]){
state^=1LL<<i;
}
}
dfs(u+1,sum+1,state);
}
}
int main(){
freopen("matchstick.in","r",stdin);
freopen("matchstick.out","w",stdout);
int T;
scanf("%d",&T);
while (T--){
int n,r;
scanf("%d%d",&n,&r);
m=2*n*(n+1);
ct=0;
memset(vis,0,sizeof(vis));
memset(belong,0,sizeof(belong));
for (int i=0,x;i<r;i++){
scanf("%d",&x);
vis[x]=true;
}
for (int sz=1;sz<=n;sz++){ // 正方形边长.cpp
for (int i=0;i+sz-1<n;i++){ // 左上角的行数.cpp
for (int j=0;j+sz-1<n;j++){ // 左上角的列数.cpp
int x0=i*(n+
