題目連結如下
http://poj.org/problem?id=1753
題目大意：
基本資訊：
給定一個4×4的正方形，每個點都放有一枚棋子，這枚棋子有兩個面，黑與白。
初始情況下：
給定16枚棋子的朝上的面，然後允許一種操作是，選中一枚棋子，将這枚棋子上下左右包括自己在内的所有棋子都翻一下面。（如果是靠邊上的棋子則可能是上左下、下右 等情況）
目标：
用最少的步數，将棋盤所有棋子都變成黑色朝上或者白色朝上。
題目分析：
分析輸入輸出
輸入很明顯，就是棋盤上的16個棋子目前朝上的面。是以用一個4×4的數組存儲即可，數組類型可以是char也可以是bool，個人覺得bool類型取反操作很贊。
輸出的話，就是最少翻面的棋子數，直接用一個int型來表示即可。
bool a[4][4];//存放棋盤目前狀态
int minn=17;//最小翻面數
分析輸出的由來
對于每個棋子都可以選擇是否翻面，被翻棋的數量可以是0~16，而且四行四列每個棋子都各自不同，每個棋子有兩種選擇翻或者不翻，是以就是2的16次方種情況。
很明顯這很适合深度優先搜尋的模闆，每一層有兩個分支。
一定要注意回溯的時候必須把翻面恢複
是以初步考慮，将這個模闆抽象出來後，就可以用深度搜尋去暴搜了。
代碼以及解釋如下：
#include<iostream>
using namespace std;
bool a[4][4];//存放棋盤目前狀态
int minn=17;//最小翻面數
//棋子上下左右
int w[5][2]={
{ 1, 0},//上
{ 0, 1},//下
{-1, 0},//左
{ 0,-1},//右
{ 0, 0}//自己
};
bool check_node(int x,int y)//判斷該節點是否合法
{
if(x<0||y<0||x>=4||y>=4)
return false;
return true;
}
bool check()//判斷目前是否滿足條件
{ bool flag=1;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
{
if(a[i][j]!=a[0][0]){
flag=0;
break;
}
}
return flag;
}
//将該節點的上下左右以及自己翻轉一下
void turn(int x,int y)
{
for(int i=0;i<5;i++)
{
int nx=x+w[i][0];
int ny=y+w[i][1];
if(!check_node(nx,ny))continue;
a[nx][ny]=!a[nx][ny];
}
}
//深度搜尋 (十六個節點的二叉樹)
void dfs(int x,int y,int z)
{
if(check())
{
if(z<minn)//更新結果
minn=z;
return;
}
if(x==4) return;
//每個節點都可以選擇翻轉或者不翻轉
turn(x,y);
//翻轉
if(y==3)dfs(x+1,0,z+1); //如果一行便利完則走下一行
else dfs(x,y+1,z+1);
//不翻轉
turn(x,y);//回溯
if(y==3)dfs(x+1,0,z);//如果一行便利完則走下一行
else dfs(x,y+1,z);
}
int main()
{
char c;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
{
cin>>c;
a[i][j] = (c=='b')?0:1;
//友善操作，正反面用0和1代替
}
dfs(0,0,0);
if(minn<17)
cout<<minn<<endl;
else
cout<<"Impossible"<<endl;
return 0;
}
進階做法：
可以考慮壓縮一下這16個棋子的表示，一提到16這個數字，我會想到short類型，剛好16位，每一位0或1表示一個棋子朝上的面是哪個。
每輸入一個棋子，則做一次左移操作即可。
那麼判斷條件也會改變
棋子全為黑或者全為白的情況如下：
因為是short類型，是以這兩種情況分别是-1和0，是以隻需要判斷該值是否等于1或者0即可。
翻牌操作也會改變
如果翻第三個棋子的話隻需要與下面的數字做異或運算即可。
代碼如下：
#include<iostream>
using namespace std;
short a=0;//16位即可
int minn=17;//最小翻面數
//棋子上下左右
int w[5][2]={
{ 1, 0},//上
{ 0, 1},//下
{-1, 0},//左
{ 0,-1},//右
{ 0, 0}//自己
};
bool check_node(int x,int y)//判斷該節點是否合法
{
if(x<0||y<0||x>=4||y>=4)
return false;
return true;
}
bool check()//判斷目前是否滿足條件
{
return(a==-1||a==0);
}
//将該節點的上下左右以及自己翻轉一下
void turn(int x,int y)
{
for(int i=0;i<5;i++)
{
int nx=x+w[i][0];
int ny=y+w[i][1];
if(!check_node(nx,ny))continue;
int w=nx*4+ny;//計算該棋子在二進制的第幾位
short num=( 1<<(15-w) );//如果是第三位，num則等于short（0010000000000000）
a^=num;//與0異或仍是本身
}
}
//深度搜尋 (十六個節點的二叉樹)
void dfs(int x,int y,int z)
{
if(check())
{
if(z<minn)//更新結果
minn=z;
return;
}
if(x==4) return;
//每個節點都可以選擇翻轉或者不翻轉
turn(x,y);
//翻轉
if(y==3)dfs(x+1,0,z+1); //如果一行便利完則走下一行
else dfs(x,y+1,z+1);
//不翻轉
turn(x,y);//回溯
if(y==3)dfs(x+1,0,z);//如果一行便利完則走下一行
else dfs(x,y+1,z);
}
int main()
{
char c;
for(int i=0;i<16;i++)
{
cin>>c;
a|=(c=='b')?0:1;
if(i!=15) a<<=1;
//正反面用0和1代替,沒輸入一次就做一次左移
}
dfs(0,0,0);
if(minn<17)
cout<<minn<<endl;
else
cout<<"Impossible"<<endl;
return 0;
}