题意：
输入一个形如：
-+-- ---- ---- -+--4*4图案，+表示close，-表示open，定义一种操作为：改变某个单元格符号（+变-，-变+），同时单元格所在行与所在列的所有单元格符号都会发生改变。
求最少操作次数能使所有单元格内都是‘-’。并输出要操作的单元格。
思路：
正常的做法和POJ 1573类似，dfs枚举即可，见code1。
这里提供一种高效的做法：
通过思考我们可以验证，某一个单元格内符号为‘+’，同时对其所在行与所在列的所有单元格进行操作（其本身只操作一次），原‘+’单元格元素便会变成‘-’，其余单元格符号均不发生改变。
所以我们可以这么做，对每个‘+’所在行列的单元格进行操作（其本身只操作一次），统计每个单元格被操作的次数，输出奇数次操作数的单元格即可。
代码参见code2.
参考：http://poj.org/showmessage?message_id=156561
AC code1（dfs）：
/*
* @author Novicer
* language : C++/C
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
#define INF 2147483647
#define cls(x) memset(x,0,sizeof(x))
#define rise(i,a,b) for(int i = a ; i <= b ; i++)
using namespace std;
const double eps(1e-8);
typedef long long lint;
int ref[6][6] = { };
int r[20],c[20];
int flag = 0 ;
int step;
vector<pair<int,int> > handle;
bool all_open(){
for(int i = 1 ; i <= 4 ; i++)
for(int j = 1 ; j <= 4 ; j++)
if(!ref[i][j]) return false;
return true;
}
void change(int row , int col){
for(int i = 1 ; i <= 4 ; i++){
ref[i][col] = !ref[i][col];
ref[row][i] = !ref[row][i];
}
ref[row][col] = !ref[row][col];
}
void dfs(int row , int col , int deep){
if(deep == step){
flag = all_open();
return;
}
if(flag) return;
if(row > 4 || col > 4) return;
r[deep] = row;
c[deep] = col;
change(row,col);
if(row < 4)
dfs(row+1 , col , deep+1);
else
dfs(1, col+1 , deep+1);
change(row,col);
if(row < 4)
dfs(row+1 , col , deep);
else
dfs(1,col+1,deep);
return;
}
void input(){
for(int i = 1 ; i <= 4 ; i++)
for(int j = 1 ; j <= 4 ; j++){
char tmp;
cin >> tmp;
ref[i][j] = (tmp == '-')? 1:0;
}
}
void solve(){
for(step = 0 ; step <= 16 ; step++){
dfs(1,1,0);
if(flag) break;
}
cout << step << endl;
for(int i = 0 ; i < step ; i++)
cout << r[i] << " " << c[i] << endl;
}
int main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w+",stdout);
input();
solve();
return 0;
}
AC code2：
/*
* @author Novicer
* language : C++/C
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
#define INF 2147483647
#define cls(x) memset(x,0,sizeof(x))
#define rise(i,a,b) for(int i = a ; i <= b ; i++)
using namespace std;
const double eps(1e-8);
typedef long long lint;
int ref[6][6] = {};
int r[20],c[20];
void work(int row , int col){
ref[row][col] = !ref[row][col];
for(int i = 1 ; i <= 4 ; i++){
ref[i][col] = !ref[i][col];
ref[row][i] = !ref[row][i];
}
}
void input(){
for(int i = 1 ; i <= 4 ; i++)
for(int j = 1 ; j <= 4 ; j++){
char tmp;
cin >> tmp;
if(tmp == '+'){
work(i,j);
}
}
}
void solve(){
int ans = 0;
for(int i = 1 ; i <= 4 ; i++)
for(int j = 1 ; j <= 4 ; j++)
if(ref[i][j]){
r[ans] = i;
c[ans] = j;
ans++;
}
cout << ans << endl;
for(int i = 0 ; i < ans ; i++)
printf("%d %d\n",r[i],c[i]);
}
int main(){
// freopen("input.txt","r",stdin);
input() ;
solve();
return 0;
}
版权声明：博主表示授权一切转载：）
POJ 2965 The Pilots Brothers' refrigerator （想法题）
原文：http://blog.csdn.net/qq_15714857/article/details/47132611