hdu 2553 N皇后问题----搜索 dfs 回溯法 预处理

hdu 2553 N皇后问题 原题链接  

   今下午看了一下八皇后问题，所以强烈的想AC一道题。。hdu上的此题 刚刚好。哈哈。

       题目大意：在一个n*n的棋盘上放置n个皇后棋子。皇后可以向行，列，对角线攻击。求皇后互不攻击的摆法有多少种。

     回溯法以前看到过名称 ，但不懂具体怎么用。 今天终于是理解一点了。回溯法的精华就是边生成边检验，所以减少了很多不必要的枚举。 具体的思路会在代码中有注释。

     这道题最直接的思路就是枚举 暴力解决，但是显然是不行的。

      所以只能用回溯。 基本思路 ，一行一行的放 皇后， 然后再递归判断是否与之前已放好的皇后有冲突，一旦有冲突，则不需要继续下一行的搜索，直接返回（省去不必要的枚举）。

       另外关于这题，还有一点，我第一次交的时候TLE了，说明测试数据特别多。所以得先预处理(这个亏吃了很多次了，牢记牢记).

在循环中递归

row

line[row]=i,(i=0,1,2,...,n)

j

 

 

//八皇后问题 回溯法
#include<stdio.h>
int tot=0,row,line[10],n;
int main()
{
    void search(int );
    int a[11];
    for(n=1;n<=10;n++) //之前就是没有这一步预处理，所以TLE了 TT
    {
        tot=0;
        search(0);
        a[n]=tot;
    }
    while(scanf("%d",&n)!=EOF&&n)
         printf("%d\n",a[n]);
    return 0;
}
void search(int row) //递归搜索可行解
{
    int i,j;
     if(row==n) tot++; //当row=n时，说明每一行的皇后都不冲突，即为可行解
     else
     for(i=0;i<n;i++)
     {
         int ok=1;
         line[row]=i; //尝试把第row行的皇后放在i列上
         for(j=0;j<row;j++) //检验是否与前面已放好的皇后冲突
         {
             if(line[row]==line[j]||line[row]-row==line[j]-j||line[row]+row==line[j]+j)
             {
                 ok=0;
                 break; //，跳出最内层循环如果冲突，停止搜索，返回上一级递归回溯。回溯法高效的关键。
             }
         }
         if(ok)
             search(row+1);
     }
}