题意:一个矩阵,每个点1或0,然后每次翻一个点,它周围上下左右(包括自己)1-》0,0-》1,问最少翻几次可以矩阵全是0,忽略题目说的字典序

分析:枚举第一行所有的情况,然后下面几行也随之确定了,然后看哪种好就行,因为每行宽最多15 所有二进制枚举一下。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<string>
using namespace std;
typedef long long LL;
const int maxn=;
const int INF=0x3f3f3f3f;
int o[maxn][maxn];
int now[maxn][maxn];
int temp[maxn][maxn];
int res[maxn][maxn];
int n,m,ans;
int dx[]= {,,-,};
int dy[]= {-,,,};
void change(int x,int y)
{
now[x][y]=-now[x][y];
for(int i=; i<; ++i)
{
int p=x+dx[i];
int q=y+dy[i];
if(p<||p>n||q<||q>m)continue;
now[p][q]=-now[p][q];
}
}
bool check(int x,int y)
{
if(now[x-][y])return true;
return false;
}
void solve(int x)
{
for(int i=; i<=n; ++i)
for(int j=; j<=m; ++j)
now[i][j]=o[i][j];
int a[maxn],cnt=,c=,flag=;
memset(temp,,sizeof(temp));
memset(a,,sizeof(a));
while(x)
{
a[++cnt]=x%;
x>>=;
if(a[cnt])++c;
}
for(int i=; i<=m; ++i)
if(a[i])change(,i),temp[][i]++;
for(int i=; i<=n; ++i)
for(int j=; j<=m; ++j)
if(check(i,j))++c,change(i,j),temp[i][j]++;
for(int i=; i<=n; ++i)
for(int j=; j<=m; ++j)
if(now[i][j])flag=;
if(!flag&&c<ans)
{
ans=c;
for(int i=; i<=n; ++i)
for(int j=; j<=m; ++j)
res[i][j]=temp[i][j];
} }
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=; i<=n; ++i)
for(int j=; j<=m; ++j)
scanf("%d",&o[i][j]);
ans=INF;
int l=(<<m);
for(int i=; i<l; ++i)
solve(i);
if(ans==INF)
{
printf("IMPOSSIBLE\n");
continue;
}
else
{
for(int i=; i<=n; ++i)
{
for(int j=; j<m; ++j)
printf("%d ",res[i][j]);
printf("%d\n",res[i][m]);
}
}
}
return ;
}

最新文章

  1. Linux 计划任务 访问网页
  2. JS网页顶部进度条demo
  3. 搭建DNS服务器
  4. POJ 1703
  5. Codeforces Round #277.5 (Div. 2)
  6. [iOS基础控件 - 6.9.1] 聊天界面Demo 代码
  7. Android源码是这样搞到的(图解)
  8. 史上最全条件编译解析 #ifdef #ifndef #undef #else #endif
  9. 3D Lut 电影级调色算法 附完整C代码
  10. IE9以及以下不支持jquery ajax跨域问题
  11. 2:Python字符串与数字
  12. Sublime Text3配置Lua运行环境
  13. collocation
  14. JavaScript:document.execCommand()的用法
  15. vue-router路由模式详解
  16. 七、CentOS 6.5 下 Nginx的反向代理和负载均衡的实现
  17. Dota2App--第三天
  18. 160314、MVC设计模式
  19. koa2 中间件里面的next到底是什么
  20. Linux实战教学笔记36:PHP服务缓存加速深度优化实践

热门文章

  1. 【BZOJ1468】Tree
  2. 线形,柱形,条形数据表(百度Echart插件)
  3. css3 简单界面动画
  4. web机制简笔
  5. 正确使用STL-MAP中Erase函数
  6. 使用jenkins自动部署java工程到jboss-eap6.3 -- 1.环境搭建
  7. CodeWars题目筛选
  8. HTML5学习(七)----地理定位
  9. 需要保存数据zabbix,不需要保存数据nagios
  10. 谈谈Runtime类中的freeMemory,totalMemory,maxMemory等几个方法