首页 > 代码库 > 1753 Flip Game

1753 Flip Game

#include<stdio.h>#include<math.h>#include<algorithm>#include<string.h>using namespace std;int pieces[10][10];int ans[16];int res[4][4];int Min=1000000;const int INF=1<<16;char ary[10];void AddOne(int a[]){    int i=0;    while(i<16)    {        a[i]+=1;        if(a[i]<2)            break;        a[i]=0;        i++;    }}bool isBorW(){    int i,j;    int c=0;    for(i=0;i<4;i++)    {        for(j=0;j<4;j++)        {            res[i][j]=pieces[i][j];        }    }    for(i=0;i<16;i++)    {        if(ans[i]==1)        {            c++;            int m=i/4;            int n=i%4;            res[m][n]=1^res[m][n];            if(m-1>=0)                res[m-1][n]=1^res[m-1][n];            if(m+1<4)                res[m+1][n]=1^res[m+1][n];            if(n-1>=0)                res[m][n-1]=1^res[m][n-1];            if(n+1<4)                res[m][n+1]=1^res[m][n+1];        }    }    for(i=0;i<4;i++)    {        for(j=0;j<4;j++)        {            if(res[i][j]!=res[0][0])            {                return false;            }        }    }    Min=Min>c?c:Min;    return true;}void print(){    int i;    for(i=0;i<16;i++)    {        printf("%d",ans[i]);    }    printf("\n");}int main(){    int i,j;    for(i=0;i<4;i++)    {        gets(ary);        for(j=0;j<4;j++)        {            if(ary[j]==b)                pieces[i][j]=1;            else                pieces[i][j]=0;        }    }    memset(ans,0,sizeof(ans));    for(i=0;i<INF;i++)    {        isBorW();    //    print();        AddOne(ans);    }    if(Min<=16)        printf("%d\n",Min);    else        printf("Impossible\n");    return 0;}/*bbww bwww wwww wwww bbww bwbw wbbb wwbw bwwbbbwbbwwbbwww*/

枚举0~2^16的所有数字,每一位代表该位上的棋子是否翻转。