Fliptile奶牛踩瓷砖 (状态压缩，开关问题，枚举)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Fliptile奶牛踩瓷砖 (状态压缩，开关问题，枚举)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1823字，纯文字阅读大概需要3分钟。
内容图文
题目：Fliptile
题意：
给定一个M*N矩阵，有些是黑色（1表示）否则白色（0表示），每翻转一个（i，j),会使得它和它周围4个格变为另一个颜色，要求翻转最少的点，使得变为全白色的矩阵，输出这个标记了翻转点的矩阵，如果有多个最优解，输出逆字典序最小的那个矩阵，若没有解，输出IMPOSSIBLE。
题解：
参考：Fliptile POJ3279 二进制压缩枚举 解题报告
只要第一行的方案确定，后面的踩发就能确定，所以状压枚举第一行的方案
代码：
/***********************************************/
int ans[30][30];
int a[34][34];
int b[33][33];
int m,n;
int ANS=inf;
ll daan=-1;
int fanzhuan1(ll Y)
{
mem0(ans);
int pp=0;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++) a[i][j]=b[i][j];
for(int i=0;i<n;i++)
{
if(Y&(1ll<<i)) //翻转第一行第n-i个
{
pp++;
ans[1][n-i]=1;
a[1][n-i]=a[1][n-i]?0:1;
if(i>0) a[1][n-i+1]=a[1][n-i+1]?0:1;
if(i<n-1) a[1][n-i-1]=a[1][n-i-1]?0:1;
if(n>1) a[2][n-i]=a[2][n-i]?0:1;
}
}
return pp;
}
void solve(int pp,ll p1)
{
for(int i=1;i<m;i++)
{
for(int j=n;j>=1;j--)
{
if(a[i][j])
{
ans[i+1][j]=1;
a[i][j]=0;
a[i+1][j]=a[i+1][j]?0:1;
if(j>1) a[i+1][j-1]=a[i+1][j-1]?0:1;
if(j<n) a[i+1][j+1]=a[i+1][j+1]?0:1;
if(i+2<=m) a[i+2][j]=a[i+2][j]?0:1;
}
}
}
for(int j=1;j<=n;j++)
{
if(a[m][j]){
//cout<<"IMPOSSIBLE"<<endl;
return ;
}
}
///取最优
int sum=pp;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
if(ans[i][j]) sum++;
}
if(sum<ANS)
{
ANS=sum;
daan=p1;
}
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin>>m>>n;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++) cin>>b[i][j];
int Y=(1<<n)-1;
for(ll i=0;i<=Y;i++)
{
int t=fanzhuan1(i);
//cout<<t<<endl;
solve(t,i);
}
if(daan==-1) cout<<"IMPOSSIBLE"<<endl;
else
{
//cout<<daan<<endl;
int t=fanzhuan1(daan);
solve(t,daan);
for(int i=1;i<=m;i++)
{
for(int j=1;j<n;j++) cout<<ans[i][j]<<" ";
cout<<ans[i][n]<<endl;
}
}
return 0;
}
原文：https://www.cnblogs.com/liuyongliu/p/10447698.html
内容总结
以上是互联网集市为您收集整理的Fliptile奶牛踩瓷砖 (状态压缩，开关问题，枚举)全部内容，希望文章能够帮你解决Fliptile奶牛踩瓷砖 (状态压缩，开关问题，枚举)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。