poj 1753题学习笔记

1753 题是一个基本的枚举算法的题，基本解题思路就是暴力枚举，但是我们需要知道即便是暴力枚举，也是需要认真分析问题的。

题意：有一个4*4的棋盘,棋盘上有黑白格,每一次你可以翻其中的一个格子。一个格子(x,y)如果被翻,它相邻的前后左右四个格子（如果在棋盘上）也要翻转。现在给你一个初始的棋盘状态，问把这个棋盘翻转到全黑或全白的最少次数；若不能达到全黑或全白，输出Impossible。

思路：只有4*4的棋盘，同时格子只有黑白两面。对于同一个格子，翻两次和不翻没有区别。同时，我们会发现，假如第一行的状态已经确定，那么剩下的行的翻法其实也是确定了的。这样我们从原来需要枚举65536种，到现在只需要枚举第一行16种即可，所以，我们只需要按照求4个数的子集的方式，枚举第一行的翻法即可枚举所有可能形式。

所以，我们需要一个子集递归方法，一个步数求解方法，还有小方法例如判断当前是否全黑或全白、将当前棋子性质翻转等，即可实现枚举。

#include <stdio.h>
#include <iostream>
#include <string>
using namespace  std;
//成功
//暴力枚举，通过枚举第一行元素的组合方式进行暴力搜索
string s[4];//输入矩阵
string tmp[4];//当前棋子状态矩阵
bool b[4];//判断枚举，1-4的子集生成
int foot=100;//步子数
void back2(int x,int y){//将tmp中的元素性质翻转，例如b转成w，w转成b
    if(tmp[x][y]=='b')tmp[x][y]='w';
    else
        tmp[x][y]='b';
}
bool test(){//判断输入矩阵是否直接为全黑或者全白
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(s[i][j]!=s[0][0])return false;
        }
    }
    return true;
}
bool test2(){//判断当前棋子矩阵是否直接为全黑或者全白
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(tmp[i][j]!=tmp[0][0])return false;
        }
    }
    return true;
}
void genera(char flag){//将当前棋子矩阵变为全黑或者全白的步数
    int root=0;
    for(int i=0;i<4;i++){//将当前状态初始化为输入状态
        for(int j=0;j<4;j++){
            tmp[i][j]=s[i][j];
        }
    }
    for(int i=0;i<4;i++){//根据第一行的子集进行转换，即改变第一行的状态
        if(b[i]){
            root++;
            back2(0,i);
            back2(1,i);
            if(i<=2)back2(0,i+1);
            if(i>=1)back2(0,i-1);
        }
        
    }
        for(int i=0;i<4;i++){//根据第一行改变第二行
        if(tmp[0][i]!=flag){
            root++;
            tmp[0][i]=flag;
            back2(1,i);
            if(i<=2)back2(1,i+1);
            if(i>=1)back2(1,i-1);
            back2(2,i);
            
        }
    }
    for(int j=2;j<4;j++){//改变第三和第四行
    for(int i=0;i<4;i++){
        if(tmp[j-1][i]!=flag){
            root++;
            tmp[j-1][i]=flag;
            back2(j,i);
            if(i<=2)back2(j,i+1);
            if(i>=1)back2(j,i-1);
            if(j<=2)back2(j+1,i);
            
        }
    }
    }
    if(test2()&&root<foot){//如果当前棋子为全黑或全白则改变最小步数
        foot=root;
    }
    
}
void gen(int y){//第一行的全部子集
    if(y==4){
        genera('b');//全黑
        genera('w');//全白
    }
    else{
        b[y]=true;//使用位向量法构造第一行的全部子集数
        gen(y+1);
        b[y]=false;
        gen(y+1);
    }
}
int main(){
    for(int i=0;i<4;i++){
        cin>>s[i];
     b[i]=false;
    }
    if(test())
        cout<<0<<endl;//判断当前是否为已经排列好的矩阵
    else
    {//构造矩阵
        gen(0);
        if(foot!=100){
            cout<<foot<<endl;
        }
        else
            cout<<"Impossible"<<endl;//如果无法生成则输出
    }
    return 0;
}

在这里，我们需要知道，即使是枚举，也需要我们动脑筋认真分析问题。