| Time Limit: 1000MS | Memory Limit: 65536K | |||
| Total Submissions: 30872 | Accepted: 11961 | Special Judge | ||
Description
There are 16 handles on the refrigerator door. Every handle can be in one of two states: open or closed. The refrigerator is open only when all handles are open. The handles are represented as a matrix 4х4. You can change the state of a handle in any location [i, j] (1 ≤ i, j ≤ 4). However, this also changes states of all handles in row i and all handles in column j.
The task is to determine the minimum number of handle switching necessary to open the refrigerator.
Input
Output
Sample Input
-+-- ---- ---- -+--
Sample Output
6 1 1 1 3 1 4 4 1 4 3 4 4
【题意】
有4×4的棋盘，上面的棋子一面是黑的，一面是白的。规定翻转一个棋子的同时也要翻转它的同行同列的棋子，问给定一个棋盘的棋子状态，至少需要翻转多少个棋子，能使得所有棋子朝上都是白的。
输出最少数，然后依次输出要翻转的棋子的位置（任意一种可行方案皆可）
【分析】
除了压缩的状态不同，其余做法与POJ 1753 Flip Game(点击查看思路）完全相同。
【代码】
#include<cstdio>
#include<iostream>
#define debug(x) cerr<<#x<<" "<<x<<‘\n‘;
using namespace std;
const int N=105;
char s[N];int now,state[]={63624,62532,61986,61713,36744,20292,12066,7953,35064,17652,8946,4593,34959,17487,8751,4383};
int top,st[N];
inline void Init(){
for(int i=0;i<4;i++){
scanf("%s",s);
for(int j=0;j<4;j++){
now<<=1;
now|=s[j]==‘+‘;
}
}
}
inline bool check(){
return !now;
}
inline void flip(int t){
now^=state[t];
}
bool find(int n,int i){
if(!n) return check();
for(;i<16;i++){
if(16-i<=n-1) break;
flip(i);st[++top]=i;
if(find(n-1,i+1)) return 1;
flip(i);top--;
}
return 0;
}
inline void Solve(){
for(int i=0;i<=16;i++){
top=0;
if(find(i,0)){
printf("%d\n",i);
for(int j=1,x,y;j<=top;j++){
x=st[j]/4+1,y=st[j]%4+1;
printf("%d %d\n",x,y);
}
return ;
}
}
puts("Impossible");
}
int main(){
Init();
Solve();
return 0;
}
POJ 2965 The Pilots Brothers' refrigerator
原文：https://www.cnblogs.com/shenben/p/10367214.html