POJ 开关问题

poj 3279 Fliptile

题目链接：http://poj.org/problem?id=3279

挑战P153

题意：有一个M*N的格子，每个格子有两种颜色，每个格子可以翻转，每翻转一个格子它以及其上下左右四个格子都会变为它相反的状态，问最少反转哪些格子可以把这些格子都变成相同的状态，解有多个时，输出字典序最小的一个

经典的开关问题，只要第一行的状态确定其他行的状态也将确定，故暴力枚举第一行的开关情况，判断最后一行的状态是否符合题意，复杂度$O(MN2^N)$,直接贴原代码

#include
#include
#include
using namespace std;
const int dx[5]={-1,0,0,0,1};
const int dy[5]={0,-1,0,1,0};
int M,N,tile[16][16],opt[16][16],flip[16][16];
int get(int x,int y){
    int c=tile[x][y];
    for(int d=0;d<5;d++){
        int x2=x+dx[d],y2=y+dy[d];
        if(0<=x2&&x2>M>>N;
    for(int i=0;i>tile[i][j];
    for(int i=0;i<1<>j&1;
        int num=calc();
        if(num>=0&&(res<0||res>num)){
            res=num;
            memcpy(opt,flip,sizeof(flip));
        }
    }
    if(res<0)
        printf("IMPOSSIBLE\n");

    else for(int i=0;i

poj3185 The Water Bowls 
题目链接：http://poj.org/problem?id=3185
题意：有20个碗依次排列，有的碗口朝上，有的碗口朝下，牛希望所有的碗口都能朝上，每次翻动某个碗时，他左边和右边的碗也会翻转到相反的状态，问要想将这些碗碗口都朝上，至少要翻动多少次。
首先没每个碗最多翻动一次，否则重复，而且碗先翻与否不影响结果，故可以贪心法从头到尾考虑每一个碗，对于没个碗，如果左边的碗朝上，则它不能翻动，反之则需要翻动，对第一个碗分翻与不翻两种情况考虑，判断最后一个碗是否朝上且取较小的值即可。

#include
#include
#include
using namespace std;
int main(){
    int a[25],b[25],ans1=1,ans2=0;
    a[0]=b[0]=0;a[21]=b[21]=1;
    for(int i=1;i<=20;i++){
        cin>>a[i];
        b[i]=a[i];
    }
        a[1]=!a[1];
        a[2]=!a[2];
    for(int i=2;i<=20;i++){
          if(a[i-1]==1){
            a[i]=!a[i];
            a[i+1]=!a[i+1];
            ans1++;
        }
    }
    for(int i=2;i<=20;i++){
          if(b[i-1]==1){
            b[i]=!b[i];
            b[i+1]=!b[i+1];
            ans2++;
        }
    }
    cout<

poj1222 EXTENDED LIGHTS OUT
题目链接：http://poj.org/problem?id=1222
题意：有一个5*6的格子，每个格子有两种颜色，每个格子可以翻转，每翻转一个格子它以及其上下左右四个格子都会变为它相反的状态，问最少反转哪些格子可以把这些格子都变成相同的状态，解有多个时，输出字典序最小的一个
经典的开关问题，只要第一行的状态确定其他行的状态也将确定，故暴力枚举第一行的开关情况，判断最后一行的状态是否符合题意

#include
#include
#include
using namespace std;
const int dx[5]={-1,0,0,0,1};
const int dy[5]={0,-1,0,1,0};
int M,N,tile[16][16],opt[16][16],flip[16][16];
int get(int x,int y){
    int c=tile[x][y];
    for(int d=0;d<5;d++){
        int x2=x+dx[d],y2=y+dy[d];
        if(0<=x2&&x2>x;M=5;N=6;
    for(int c=1;c<=x;c++){
    for(int i=0;i>tile[i][j];
    for(int i=0;i<1<>j&1;
        int num=calc();
        if(num>=0){
            res=num;
            memcpy(opt,flip,sizeof(flip));
        }
    }
    cout<<"PUZZLE #"<