POJ1965 The Pilots Brothers' refrigerator（dfs，回溯，枚举）

POJ2965
题意分析：
有个4*4的0/1图，初始状况是随机的。每次可以选16个位置中的一个位置翻，每翻一次，该位置所在的行和列的所有值都被取反，问要至少翻几次才能把它翻成全是减号。

和POJ1753类似，这里用的dfs+回溯法写的，先把格子转换成0/1图，然后dfs即可。

2019年2月23日

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define maxn 10010
using namespace std;
char ch;
int mp[maxn][maxn],ansx[maxn],ansy[maxn],x[maxn],y[maxn];
int ans=33;void flip(int ss){
    int tx=ss/4;int ty=ss%4;for(int i=0;i<4;i++){
    mp[tx][i]=1-mp[tx][i];mp[i][ty]=1-mp[i][ty];}mp[tx][ty]=1-mp[tx][ty];    //被重复翻了2次
}bool complete(){
    for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
    if(mp[i][j]==1) return false;}}return true;
}
//s表示当前处理的格子，b表示翻转的次数
void dfs(int s,int b){
    if(complete()){
    if(ans>b){
      //最多翻转33次ans=b;for(int i=1;i<=ans;i++){
    ansx[i]=x[i];ansy[i]=y[i];}return ;}}if(s>=16) return ;dfs(s+1,b);flip(s);x[b+1]=s/4+1;y[b+1]=s%4+1;dfs(s+1,b+1);flip(s);        //回溯
}
int main(){
    std::ios::sync_with_stdio(false);for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
    cin>>ch;if(ch=='+'){
    mp[i][j]=1;}else if(ch=='-') {
    mp[i][j]=0;}}}dfs(0,0);cout<<ans<<endl;for(int i=1;i<=ans;i++){
    cout<<ansx[i]<<" "<<ansy[i]<<endl;}return 0;
}

dfs+回溯：

#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
int x[20],y[20]; //临时路径
int ansX[20],ansY[20]; //最终路径
int ans=33;  //最多翻转33次int mp[5][5];
void init(){
    char ch;for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
    cin>>ch;if(ch=='-') mp[i][j]=1;else mp[i][j]=0;}}
}bool complete(){
    for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
    if(mp[i][j]==0) return false;}}return true;
} 
void flip(int s){
    int x1=s/4;int y1=s%4;for(int i=0;i<4;i++){
    mp[i][y1]=!mp[i][y1];mp[x1][i]=!mp[x1][i];}mp[x1][y1]= !mp[x1][y1];
}
void dfs(int s,int b){
      //s代表当前处理的格子，b代表翻转格子次数if(complete()){
    if(ans>b){
     //最多翻转an=33次ans=b;for(int i=1;i<=ans;i++){
    ansX[i]=x[i];ansY[i]=y[i];}return ;}}if(s>=16) return ;dfs(s+1,b); //不管第s个格子，直接向下找flip(s);  //翻转第s个格子x[b+1]=s/4+1;  //临时路径y[b+1]=s%4+1;dfs(s+1,b+1);flip(s); //回溯
}int main(){
    init();dfs(0,0);cout<<ans<<endl;for(int i=1;i<=ans;i++){
    printf("%d %d\n",ansX[i],ansY[i]);}return 0;
}