这次说的又有点新鲜的东西。

那就是回溯了。

本题是一个经典回溯例题，注意体会一下OK,

那么我们说说他有什么用呢？

其实很简单了，它的作用就是控制DFS的搜索流程。

在本题简单一点来说，就是它能使得DFS符合题意。

直接看例子吧。

题目：HDU 1045  

题意：这个是一个八皇后的变种。不算难。

Sample Input:

4

.X..

....

XX..

....

Sample Output:

5

 

#include
      
        #include
       
         #include
        
          #include
         
           using namespace std; char Map[5][5]; int N,  Max; bool OK(int x, int y) {
    int i, j; for(i=x-1; i>=0; i--)     {
    if(Map[i][y]=='N') return false; else if(Map[i][y]=='X') break;     } for(j=y-1; j>=0; j--)     {
    if(Map[x][j]=='N') return false; else if(Map[x][j]=='X') break;     } return true; } void DFS(int Pos, int C) {
    if(Pos==N*N)     {
    if(C>Max) Max=C; return;     } int i=Pos/N, j=Pos%N; if(Map[i][j]=='.' && OK(i, j))     {
            Map[i][j]='N';         DFS(Pos+1, C+1);         Map[i][j]='.'; //回溯 回溯 回溯 回溯     }     DFS(Pos+1, C); return; } int main() {
    int i, j; while(cin>>N && N)     {
    for(i=0; i
          
           >Map[i][j];         Max = 0;         DFS(0, 0);         cout<
           
            <