支配剧场
题目背景
May all the beauty be blessed.
题目描述
布洛妮娅和符华在寻找琪亚娜的途中，被支配之律者困在了支配剧场的高塔回廊之中。布洛妮娅敏锐地发现，虚无回廊是由一些支配之律者生成的积木构成的，只要击碎其中一些积木，就能解除空间的限制，让她们逃出高塔回廊。
具体来说，整个高塔回廊可以由一张高为 n n n，宽为 m m m 的地图表示。第 1 1 1 行为空间的最高点，第 n n n 行为空间的最低点。高塔由 K K K 块积木堆叠而成，符华每次可以击碎高塔中任意的积木，但必须保证高塔不会倒塌（否则她们会落入虚数空间），以及击碎积木后，高塔回廊的高度不变（即不能把最顶层的积木全部击碎）。
如果一块积木最底层的长度是 L L L，那么当且仅当其最底层与地板或者其他积木的接触面积 L ′ L' L′ 满足 L ′ ≥ ⌈ L 2 ⌉ L' \ge \left\lceil \frac{L}{2} \right\rceil L′≥⌈2L⌉ 时，这块积木不会失去平衡。当所有积木都不失去平衡时，我们认为整个高塔回廊不会倒塌。
积木的最底层长度被定义为积木行坐标最大的方块总个数。例如：
0 1 0
1 1 1
0 1 0
这张图中， 1 1 1 号积木的最底层长度是 1 1 1，因为其所占的格子中，行坐标最大的只有一个格子 ( 3 , 2 ) (3,2) (3,2)。
请帮布洛妮娅计算一下，符华最多能击碎多少个积木？
输入格式
第一行两个整数 n , m n,m n,m, 表示地图范围。
接下来 n n n 行，每行 m m m 个整数。第 i i i 行第 j j j 个整数 a i , j a_{i,j} ai,j，表示第 i i i 行第 j j j 列的格子属于第 a i , j a_{i,j} ai,j 块积木。若 a i , j = 0 a_{i,j} = 0 ai,j=0，则这个位置是空的。
输出格式
一行一个整数，表示符华能击碎的最多的积木块数。
样例 #1
样例输入 #1
5 3
2 2 2
2 3 1
2 3 1
2 3 1
1 1 1
样例输出 #1
1
样例 #2
样例输入 #2
5 5
0 0 2 2 2
3 3 2 2 2
3 3 3 2 2
1 2 2 2 4
1 1 1 2 4
样例输出 #2
3
提示
1 ≤ n , m ≤ 30 1\leq n,m\leq 30 1≤n,m≤30，积木块数 K K K 满足 1 ≤ K ≤ 15 1\leq K \leq 15 1≤K≤15，且保证高塔初始一定不会倒塌，同一块积木一定是一个四联通块。
【样例 1 解释】
符华可以击碎 3 3 3 号积木，这不会导致高塔坍塌，也不会降低高塔的高度。可以证明没有更优的方案。
【样例 2 解释】
可以击碎 1 , 3 , 4 1,3,4 1,3,4 号积木。
思路：
纯唐型，检查了一个小时为什么会WA，最后发现题目条件是要求塔的高度不能降低而不是塔高要为n。
n，m都较小，所以不需要太多算法，直接暴力dfs枚举可能删除积木的情况即可，就是实现的细节可能比较多…虽然考场上也没仔细想这个题，只觉得麻烦就放弃了去做别的，然后别的也没做出来。
另外，除夕夜了自己还在补题~，单纯是因为闲得无聊，那就祝看到这里的人新年快乐，蛇年大吉。
#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;
using namespace std;
int a[35][35];
int k[50],bj[50];
vector<int> c;
int ans = 0 ;
int n,m,cnt=0;
vector<int>bh;
int cbh[50];
int hst=0;
bool check(){// cout<<"check:";// for(int e:c)cout<<e<<" ";// cout<<endl;if(c.size()==0)return false;bool bd = 0;for(int i=1;i<=m;i++){if(bj[a[hst][i]]){bd=1;// cout<<"wd"<<endl;break;}}if(!bd) return false;for(int e : c){if(k[e]==n)continue;int cd=0,cj=0; for(int i=1;i<=m;i++){ if(a[k[e]][i] == e){cd++;if(bj[a[k[e]+1][i]])cj++;}}// cout<<e<<" "<<cj<<" "<<cd<<endl;if(cj*2<cd){bd=0;break;}}return bd;
}void dfs(int cz,int x){if(x==cnt){if(cz!=0 && check()){// cout<<"-cg : "<<cnt-cz<<endl;ans = max(ans,cnt-cz);}return;};bj[bh[x+1]]=1;c.push_back(bh[x+1]);dfs(cz+1,x+1);bj[bh[x+1]]=0;c.pop_back();dfs(cz,x+1);
}signed main() {cin.tie(0)->ios::sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];if(hst ==0 && a[i][j]!=0 )hst = i;if(cbh[a[i][j]]==0){bh.push_back(a[i][j]);cbh[a[i][j]]=1;}}}if(cbh[0]==0)bh.push_back(0);cnt = bh.size()-1;sort(bh.begin(),bh.end());for(int i=n;i>=1;i--){for(int j=1;j<=m;j++){if(k[a[i][j]] == 0){k[a[i][j]]=i;}}}dfs(0,0);cout<<ans;// cout<<endl<<a[1][5]<<" "<<bj[a[1][5]];return 0;
}
