D - Fliptile
2024-08-30 08:28:01
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std; const int INF = 0xfffffff;
int g[][];
int f[][] = {};
int ans[][] = {};
int mmin = INF; bool judge(int n,int m)//判断最后一行是否全为0
{
for(int i=;i<=m;i++)
{
int t = f[n][i]+f[n][i-]+f[n][i+]+f[n-][i];
if( (g[n][i]+t)& )
return false;
}
return true;
} void dfs(int n,int m,int k,int num)
{
if(num > mmin)//剪枝
return;
if(k > n)
{
if(judge(n, m) && mmin>num)//判断是否符合条件
{
memcpy(ans, f, sizeof(f));
mmin = num;
}
return;
}
int t = ;
for(int i=;i<=m;i++)
{
if((g[k-][i]+f[k-][i]+f[k-][i-]+f[k-][i+]+f[k-][i])&)//上一行是否为1,即是否需要翻转
{
f[k][i] = ;
t++;
}
else
f[k][i] = ;
}
dfs(n, m, k+, num+t);
} //n,m行列数 k当前列 num第一行翻转的次数
void todfs(int n, int m, int k, int num)
{
if(k > m)
{
dfs(n, m, , num); //对第一行每种情况进行搜索
return;
}
f[][k] = ; //不翻转
todfs(n, m, k+, num);
f[][k] = ; //翻转,num+1
todfs(n, m, k+, num+);
} int main()
{
int n,m;
cin >> n >> m;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
cin>>g[i][j];
todfs(n, m, , ); //递归遍历第一行所有情况
if(mmin == INF)
cout<<"IMPOSSIBLE"<<endl;
else
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
cout<<ans[i][j]<<" ";
cout<<endl;
}
return ;
}
最新文章
- 第一个C语言程序
- DBA-mysql-表
- 一道打印M的面试题
- git详细教程
- 2.Linq实用性技巧篇
- [King.yue]VS2012 无法启动IIS Express Web服务器的解决方案
- Android的十六进制颜色值
- 牛腩新闻发布系统--学习Web的小技巧汇总
- Redis笔记-单机版安装
- js判断浏览器是否支持webGL
- HTML5-Input
- context-param和init-param的区别
- [web][nginx] 初识nginx -- 使用nginx搭建https DPI解码测试环境
- Windows jmeter配置
- Java实现的简单神经网络(基于Sigmoid激活函数)
- 文本处理三剑客之 awk
- Python实现 K_Means聚类算法
- Hexo之我的桌角女友的食用方式
- CodeForces-Zuhair and Strings(思维+枚举)
- 跟着Sedgewick学算法(week 1 UnionFind)
热门文章
- 谈谈EJB是怎样公布Web Service的
- linux shell执行远程计算机上的命令或者脚本(ssh)
- BestCoder Round #92 1001 Skip the Class —— 字典树 or map容器
- HDU6025 Coprime Sequence —— 前缀和 & 后缀和
- 常用的PHP类库,PHP开发者必备【转】
- Oracle中的关键字
- vue中的 v-if VS v-show
- mac上Firefox安装firebug和firepath
- Algorithm-4th part I 学习进度 (7/12)
- 3-C++程序的结构1.4