2025-10-10 16:43:22
发布于：香港
8阅读
0回复
0点赞
版本1
这里同样是一个01枚举，只需要枚举每一个摊位选或不选，并在选的情况下更新状态即可，对于字符串某一位的状态，只要有一个选择的摊位有 o，那么这个位置状态就是 o 了，即我们只要摊位状态遇到了o，那么就去更新我们的状态即可。
结合注释看代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int ans=10; //记录最小摊位数量，注意初始化至少要>=可能答案的最大值。
string target=""; //目标字符串，相当于最后我们要得到一个长度为 m 的全为'o'的字符串
string s[12]; //存储每个摊位的字符串
int cnt;
void dfs(int p,string res){
if(p>n){
if(res==target){ //符合要求，开始取 min 值
ans=min(ans,cnt);
}
return ;
}
//选第 p 个摊位
string res1 = res; //为了方便消除影响，干脆复制一个字符串副本，在这修改并传入下一层
for(int i=0;i<m;i++){
if(s[p][i]=='o'){
res1[i]='o';
}
}
cnt++;
dfs(p+1,res1); //注意这里传入的是字符串 res1
cnt--;
//不选，没有任何影响，直接进入下一层即可
dfs(p+1,res);
}
signed main(){
cin>>n>>m;
string ss=""; //这个是dfs的初始状态字符串，只需要保证长度为 m 并且字符没有'x'即可
for(int i=0;i<m;i++){
target+='o';
ss+='x';
}
for(int i=1;i<=n;i++){ //输入
cin>>s[i];
}
dfs(1,ss); //深搜枚举，从第 1 层开始，当前状态字符串
cout<<ans; //输出
return 0;
}
版本2
下面的题解中用到了或运算，在二进制视角下，或运算的运算规则如下：
101001
or 010011
=> 111011
即按低位对齐后，有 则 ，全 为 。
这种方式优化了上述代码中需要用循环的方式来更新状态这一步，而且也可以比较巧妙地知道最终目标状态就是 个 ，而 的结果刚好就是 个 。
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=10;
int a[12];
int cnt;
void dfs(int p,int res){
if(p>n){
if(res==(1<<m)-1){
ans=min(ans,cnt);
}
return ;
}
dfs(p+1,res);
cnt++;
dfs(p+1,res|a[p]); //二进制的或运算
cnt--;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
string s;
cin>>s;
for(int j=0;j<m;j++){
a[i]+=(s[j]=='o'?1:0)<<j; //把 'o,x'看作 '1,0'的二进制表达，
}
}
dfs(0,0);
cout<<ans;
return 0;
}
这里空空如也
有帮助，赞一个