1139.txt

集合了SOJ（四川大学ACM在线评测系统）众多经典题目的详细解题报告

Flip Game
题意：
    在一个4*4的棋盘内的每一块方格中放一个黑白棋，一面是黑，一面是白，每次可翻动一个棋子，同时与其相邻的棋子也会翻面，要求出最少步数使得棋盘内的棋子变成同样的颜色（全黑或全白）。
解法：
    此题与wiltord讨论后解出。可用两种解法，一种是直接搜索，由于共有16个棋子，每个棋子有2种状态，所以共有2^16个结点，由于测试数据不大，所以可以在ms级内将结果得出。
    另一种方法是由hunter提出的，即要使所有棋子成为同色，则对于第一排棋子即2^4种状态搜索完后，以下每一排的状态已经由其前一排的状态决定，最终达到所有的棋子都同色。也就是说，当第一排得到一种状态后，第二排的状态必须保证第一排的棋子都为白或黑，第三排保证第二排，第四排保证第三排。故实际只须搜索16个结点，使速度提高！