HDOJ2553-N皇后问题(DFS)

N皇后问题

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12279 Accepted Submission(s): 5535

Problem Description

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。

Input

共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。

Output

共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

Sample Input

Sample Output

1
92
10

Author

cgf

Source

2008 HZNU Programming Contest

知识点:DFS 回溯法（可见http://www.cnblogs.com/ZP-Better/p/4649694.html）

题意：见题目描述(obviously)

思路：DFS 先找状态(目前所在第几行，目前所在第几列，目前已经放置的皇后数量）扩展方式：从第一列到最后一列搜索到合适的位置，最终状态：目前放置的皇后数量等于题目所要求的皇后数量。

重点:1.如何判断2个皇后不允许不允许处在与棋盘边框成45角的斜线上。将棋盘看成坐标图，row1+column1=row2+column2=c(x1+y1=x2+y2=c) or row1-column1=row2-column2=c(x1-y1=x2-y2=c)来判断2个皇后是否在棋盘边框成45角的斜线上。为了满足这个条件还需要将目前这个点与已经放置过的点(需要遍历前面的点）判断才满足。

2.这题卡时间，又由于数字较小所以要打表将这10种情况用数组存下。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 int n,cnt;
 6 int vis[11];//标记数组
 7 int picture[11];//用下标来表示行号，自身存储列号。
 8 bool judge(int r,int r2,int c2)//判断2个皇后是否在棋盘边框成45角的斜线上
 9 {
10     for(int i=0;i<=r;i++)//遍历已经放置皇后的点
11     {
12     if(i+picture[i]==r2+c2||i-picture[i]==r2-c2)
13         return false;
14     }
15     return true;
16 }
17 void dfs(int row,int column,int num)
18 {
19     if(num==n)
20     {
21     cnt++;
22     return;
23     }
24     for(int i=0;i<n;i++)
25         if(!vis[i]&&judge(row,row+1,i))
26         {
27             picture[row+1]=i;
28             //printf("%dorz%dorz%d
",row+1,i,num);
29             vis[i]=1;
30             dfs(row+1,i,num+1);
31             vis[i]=0;
32         }
33 }
34 int main()
35 {
36     while(~scanf("%d",&n))
37     {
38     cnt=0;
39     memset(vis,0,sizeof(vis));
40     memset(picture,0,sizeof(picture));
41     for(int i=0;i<n;i++)
42     {
43      vis[i]=1;
44      picture[0]=i;
45      dfs(0,i,1);
46      vis[i]=0;//回溯法：还原标记
47     }
48     printf("%d
",cnt);
49     }
50     return 0;
51 }

通过上面代码得到10种情况答案。下面是AC代码

 1 #include <cstdio>
 2 #include <iostream>
 3 int a[100]={1,1,0,0,2,10,4,40,92,352,724};
 4 int n;
 5 int main()
 6 {
 7   while(~scanf("%d",&n))
 8   {if(n==0)
 9   break;
10   printf("%d
",a[n]);}
11   return 0;
12 }