轉載標明出處：http://blog.csdn.net/lyy289065406/article/details/6642595#comments

本題難點有兩個，一個就是不要以全黑（或全白）作為目標進行搜索，而是要把全黑（或全白）作為“根”，去搜索樹葉，看看是否有 輸入的棋盤狀態。

?另一個難點需要一點數學功底，就是要知道 樹 的最大高度，這是“狀態不存在”的判斷標準

提示：其實每格棋子最多只可以翻轉一次（實際是奇數次，但這沒意義），只要其中一格重復翻了2次(不論是連續翻動還是不連翻動)，那么它以及周邊的棋子和沒翻動時的狀態是一致的，由此就可以確定這個棋盤最多只能走16步，最多只能有翻出2^16種狀態

AC:

#include<iostream> using namespace std;bool chess[6][6]={false};//利用的只有中心的4x4 bool flag; int step; int r[]={-1,1,0,0,0};//便于翻棋操作 int c[]={0,0,-1,1,0};bool judge_all(void)//判斷“清一色” {int i,j;for(i=1;i<5;i++)for(j=1;j<5;j++)if(chess[i][j]!=chess[1][1])return false;return true; }void flip(int row,int col)//翻棋 {int i;for(i=0;i<5;i++)chess[row+r[i]][col+c[i]]=!chess[row+r[i]][col+c[i]];return; }void dfs(int row,int col,int deep) //深搜的迭代回溯是重點，很容易混亂 {if(deep==step){flag=judge_all();return;}if(flag||row==5)return;flip(row,col); //翻棋if(col<4)dfs(row,col+1,deep+1);elsedfs(row+1,1,deep+1);flip(row,col); //不符合則翻回來if(col<4)dfs(row,col+1,deep);elsedfs(row+1,1,deep);return; }int main(void) {char temp;int i,j;for(i=1;i<5;i++)for(j=1;j<5;j++){cin>>temp;if(temp=='b') chess[i][j]=true;}for(step=0;step<=16;step++) //對每一步產生的可能性進行枚舉{ //至于為什么是16，考慮到4x4=16格，而每一格只有黑白兩種情況，則全部的可能性為2^16dfs(1,1,0);if(flag) break;}if(flag)cout<<step<<endl;elsecout<<"Impossible"<<endl;return 0; }

總結

以上是生活随笔為你收集整理的poj 1753的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。