枚举 POJ 1753 Flip Game

题目地址：http://poj.org/problem?id=1753

 /*

     这题几乎和POJ 2965一样，DFS函数都不用修改

     只要修改一下change规则。。。

     注意：是否初始已经ok了要先判断

 */

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <cmath>

 #include <string>

 #include <map>

 #include <queue>

 #include <vector>

 using namespace std;

 const int MAXN = 1e6 + ;

 const int INF = 0x3f3f3f3f;

 int a[][];

 bool flag;

 bool ok(void)

 {

     int tmp = a[][];

     for (int i=; i<=; ++i)

     {

         for (int j=; j<=; ++j)

             if (a[i][j] != tmp)    return false;

     }

     return true;

 }

 void change(int x, int y)

 {

     a[x][y] = !a[x][y];

     if (x > )    a[x-][y] = !a[x-][y];

     if (x < )    a[x+][y] = !a[x+][y];

     if (y > )    a[x][y-] = !a[x][y-];

     if (y < )    a[x][y+] = !a[x][y+];

 }

 void DFS(int x, int y, int num, int cnt)

 {

     if (num == cnt)

     {

         flag = ok ();

         return ;

     }

     for (int i=x; i<=; ++i)

     {

         int j;

         if (i == x)    j = y + ;

         else    j = ;

         for (; j<=; ++j)

         {

             change (i, j);

             DFS (i, j, num+, cnt);

             if (flag)    return ;

             change (i, j);

         }

     }

 }

 void work(void)

 {

     if (ok ())

     {

         printf ("%d\n", );        return ;

     }

     int cnt;

     for (cnt=; cnt<=; ++cnt)        //最多16次，可以暴力枚举

     {

         flag = false;

         DFS (, , , cnt);

         if (flag)    break;

     }

     (cnt <= ) ? printf ("%d\n", cnt) : puts ("Impossible");

 }

 int main(void)        //POJ 1753 Flip Game

 {

     //freopen ("A.in", "r", stdin);

     char ch;

     for (int i=; i<=; ++i)

     {

         for (int j=; j<=; ++j)        //b-0 w-1

         {

             scanf ("%c", &ch);

             a[i][j] = (ch == 'b') ?  : ;

         }

         getchar ();

     }

     work ();

     return ;

 }

 /*

 Impossible

 */