题意

游戏“The Pilots Brothers:跟随有条纹的大象”有一个玩家需要打开冰箱的任务。

冰箱门上有16个把手。每个手柄可以处于以下两种状态之一:打开或关闭。只有当所有把手都打开时,冰箱才会打开。手柄表示为矩阵4х4。您可以在任何位置[i,j](1≤i,j≤4)更改句柄的状态。但是,这也会更改第i行中所有句柄的状态以及第j列中的所有句柄。

任务是确定打开冰箱所需的最小手柄切换次数。

思路

一个和“费解的开关”,"棋盘翻转",这样的位运算的题目很像,只不过这次一次翻转1行+1列

其实可以用1个数就可以记录状态,但是我懒……

(其实是不会状压啦)

Code

#include<cstdio>
using namespace std;
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b) int x[], y[]; int map[][];
int ans=;
int ansX[],ansY[]; int read()
{
char ch = getchar();
while (ch!='-' && ch!='+') ch = getchar();
return ch=='-'?:;
} void build()
{
for(int i=;i<;i++)
for (int j = ; j < ; j++)
map[i][j] = read();
} void flip(int s)
{
int x1 = s / ;
int y1 = s % ;
for (int i = ; i < ; i++)
{
map[i][y1] ^= ;
map[x1][i] ^= ;
}
map[x1][y1] ^= ;
} bool check()
{
for (int i = ; i < ; i++)
{
for (int j = ; j < ; j++)
if (!map[i][j]) return ;
}
return ;
} void dfs(int s, int b)
{
if (check())
{
if (ans > b)
{
ans = b;
for (int i = ; i <= ans; i++)
ansX[i] = x[i], ansY[i] = y[i];
}
return;
} if (s >= ) return;
dfs(s + , b);
flip(s);
x[b + ] = s / + ;
y[b + ] = s % + ;
dfs(s + , b + );
flip(s);
return;
} int main()
{
build();
dfs(, );
printf("%d\n", ans);
for (int i = ; i <= ans; i++)
printf("%d %d\n", ansX[i], ansY[i]);
return ;
}

其他做法

博客上搜到的

放出来

注释也很详细了

用奇偶性做的

/*

参考高手的高效解法:
> 证明:要使一个为'+'的符号变为'-',必须其相应的行和列的操作数为奇数;可以证明,如果'+'位置对应的行和列上每一个位置都进行一次操作,则整个图只有这一'+'位置的符号改变,其余都不会改变.
> 设置一个4*4的整型数组,初值为零,用于记录每个点的操作数,那么在每个'+'上的行和列的的位置都加1,得到结果模2(因为一个点进行偶数次操作的效果和没进行操作一样,这就是楼上说的取反的原理),然后计算整型数组中一的
> 个数即为操作数,一的位置为要操作的位置(其他原来操作数为偶数的因为操作并不发生效果,因此不进行操作)
*********************************
此上证其可以按以上步骤使数组中值都为‘-’
********************************
在上述证明中将所有的行和列的位置都加1后,在将其模2之前,对给定的数组状态,将所有的位置操作其所存的操作数个次数,举例,如果a[i][j]==n,则对(i,j)操作n次,当所有的操作完后,即全为‘-’的数组。
其实就是不模2的操作,作了许多的无用功。
以上的操作次序对结果无影响,如果存在一个最小的步骤,则此步骤一定在以上操作之中。(简单说下:因为以上操作已经包含了所有可改变欲改变位置的操作了)
而模2后的操作是去掉了所有无用功之后的操作,此操作同样包含最小步骤。
但模2后的操作去掉任何一个或几个步骤后,都不可能再得到全为‘-’的。(此同样可证明:因为操作次序无影响,先进行最小步骤,得到全为‘-’,如果还剩下m步,则在全为‘-’的数组状态下进行这m步操作后还得到一个全为
‘-’的数组状态,此只能是在同一个位置进行偶数次操作,与前文模2后矛盾,所以m=0),因此模2后的操作即为最小步骤的操作。
*/
#include <iostream>
using namespace std; bool mark[][];
char s[][]; int main()
{
int i,j,k;
int ci[],cj[];
int nas = ;
memset(mark,,sizeof(mark));
for(i = ;i < ;i++)
cin >> s[i];
for(i = ;i < ;i++)
for(j = ;j < ;j++)
{
char c = s[i][j];
if(c == '+')
{
mark[i][j] = !mark[i][j];
for(k = ;k < ;k++)
{
mark[i][k] = !mark[i][k];
mark[k][j] = !mark[k][j];
}
} }
for(i = ;i < ;i++)
for(j = ;j < ;j++)
if(mark[i][j] == true)
{
ci[nas] = i + ;
cj[nas] = j + ;
nas ++;
}
printf("%d\n",nas);
for(i = ;i < nas;i++)
{
printf("%d %d\n",ci[i],cj[i]);
}
return ;
}

最新文章

  1. C++中new,delete和new[] ,delete[]的分析
  2. SQL Server 临时禁用和启用所有外键约束(高版本向低版本迁移数据)
  3. Coursera台大机器学习课程笔记4 -- Training versus Testing
  4. c#根据后台数据,自动生成checkbox
  5. 1-4-1 Windows应用程序组成及编程步骤
  6. 每天一水SGU347
  7. CCNA实验(2) -- Static Route
  8. python_cookie
  9. CSS之 absoulte 属性
  10. .NET采集数据,放入数据库总结
  11. Python档案袋(生成器、迭代器、队列 )
  12. vs2017开发IOS(vs2017 xamarin 连接mac)
  13. OFBiz项目简介
  14. Hadoop记录-Hadoop集群添加节点和删除节点
  15. InnoDB中锁的查看
  16. Asp.Net4.5 mvc4(二) 页面创建与讲解
  17. Intelij的idea和pycharm的使用
  18. PLY文件格式
  19. web前端的问题整理
  20. MySQL表名大小写设置

热门文章

  1. 删除链表倒数第n个节点
  2. epoll ET(边缘触发) LT(水平触发)
  3. 应用调试(四)系统调用SWI
  4. saltstack主机管理项目:今日总结(六)
  5. mysql 端口修改
  6. swiper常见问题
  7. 迭代器模式-Iterator(Java实现)
  8. ACM-ICPC 2018 徐州赛区网络预赛 B BE, GE or NE(记忆化搜索)
  9. tolua之wrap文件的原理与使用
  10. 深入浅出mybatis之启动详解