题意简述

4*4的格子放有黑白两面的棋子16个，翻转任一棋子会使其上下左右棋子一同翻转。给定初始状态，求达到所有棋子全黑或全白的最少翻转次数。如果无解，输出Impossible。

算法分析

首先容易证明：

1、翻转棋盘上任意个棋子，棋盘达到的状态与各棋子被翻转的先后顺序无关。

2、对每个棋子进行2次及以上的翻转没有意义。∵ 偶数次翻转结果与不翻转相同，奇数次翻转结果与翻转1次相同。

于是问题被简化为：棋盘上部分棋子经过1次翻转，能使棋盘达到全黑或全白状态。求所需翻转棋子的最少数目。

因为一共只有16个棋子，故只有2^16种可能。

——————————————————————分割线——————————————————————

具体算法：

DFS。

输入时将数据转化为1维01数组。

dfs(array,position,step,answer)四个形参，array传递数组，position传递当前位置，step传递深度（也即翻转个数），ans传递当前最优答案。

深搜时先判断当前状态是否满足条件，满足则和当前答案对比，若更优则替换。返回。

若深度超出16也返回。

改变当前位置，以及上下左右共5个点状态。

dfs(array,position+1,step+1,answer)。

回溯。只需再次改变5个点状态即可。

dfs(array,position+1,step,answer)。

Problem Status: AC。时间94ms，内存360k

——————————————————————分割线——————————————————————

TIPS:

WA了好几次。有几个小细节要注意：

1、翻转时，如果遇到行末则不翻转下一个，遇到行首则不翻转上一个。可以通过mod 4的值来判断。

2、DFS时，需先判断是否满足条件（全黑或全白）再判断位置是否越界（position<16）。因为有可能所有棋子都需要翻转，由于判断本次翻转是否成功是在下一层递归中，所以即使position越界也需先验证一次上次翻转后是否达到所需状态。

——————————————————————分割线——————————————————————

优化：

1、一维01数组可以使用一个int类型变量替代。2个字节16位就可以表示了。翻转操作采用位运算实现。（这个还没试过，据说时间达到16ms，以后有机会试下。）

2、网上的解题报告说据说有一种枚举可以达到时间0ms？还没找到具体算法。要去膜拜下。

程序样例

#include

void change(int s[],int pos)
{
    if (s[pos]==0) s[pos]=1; else s[pos]=0;
    if ((pos+1<16)&&(pos%4!=3))
        if (s[pos+1]==0) s[pos+1]=1; else s[pos+1]=0;
    if ((pos-1>=0)&&(pos%4!=0))
        if (s[pos-1]==0) s[pos-1]=1; else s[pos-1]=0;
    if (pos+4<16)
        if (s[pos+4]==0) s[pos+4]=1; else s[pos+4]=0;
    if (pos-4>=0)
        if (s[pos-4]==0) s[pos-4]=1; else s[pos-4]=0;
}

int finish(int s[])
{
    int i;
    for(i=1;i<16;i++)
        if (s[i]!=s[0]) return 0;
    return 1;
}

void try(int s[], int pos, int step, int *ans)
{
    if (finish(s))
    {
        if (step<*ans) *ans=step;
        return;
    }
    if (pos>15) return;
    change(s,pos);
    try(s,pos+1,step+1,ans);
    change(s,pos);
    try(s,pos+1,step,ans);
}

int main()
{
    int s[16];
    int i,j,ans=17;
    char t[5];
    for(i=0;i<4;i++)
    {
        scanf("%s",t);
        for(j=0;j<4;j++)
            if (t[j]=='b') s[i*4+j]=1;
            else s[i*4+j]=0;
    }
    try(s,0,0,&ans;);
    if (ans==17) printf("Impossible"); else printf("%d",ans);
    system("pause");
    return 0;
}