hdu 2553 N皇后问题 （经典的dfs）

N皇后问题

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

 

Problem Description

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

 

Input

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

 

Output

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

 

Sample Input

1
8
5
0

 

Sample Output

1
92
10

      

        又是一个经典的dfs问题！非常值得大家去学习的一条题目！想当年刚刚大一时，觉得8皇后问题非常难且复杂，但是知道了dfs这个算法后，原来这是如此的简单！！！

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2553

我的代码（有注释）：

//经典的N皇后问题
#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;

int ch[25][25];
int n, num, result[25];

void dfs(int x, int y)
{
    if(ch[x][y]) return;    //如果该点已经被攻击，则返回
	int i, xx, yy;
    if(x == n)  //如果
    {
        num++;
        return;
    }

    //下面个人觉得比较巧妙，因为会有重复的地方很难分析是属于哪个皇后
    //若用了下面位置的 ++ or -- ，则巧妙地避免上述情况
    //一共八个方向进行标记：上、下、左、右、左上、左下、右上、右下
    xx = x; yy = y;
    while(xx>0)  ch[xx--][y]++;
    xx = x; yy = y;
    while(yy>0)  ch[x][yy--]++;
    xx = x; yy = y;
    while(xx<=n) ch[xx++][y]++;
    xx = x; yy = y;
    while(yy<=n) ch[x][yy++]++;
    xx = x; yy = y;
    while(xx<=n && yy<=n) ch[xx++][yy++]++;
    xx = x; yy = y;
    while(xx>0  && yy<=n) ch[xx--][yy++]++;
    xx = x; yy = y;
    while(xx<=n && yy>0)  ch[xx++][yy--]++;
    xx = x; yy = y;
    while(xx>0  && yy>0)  ch[xx--][yy--]++;

    for(i = 1; i <= n; i++)
    {
        dfs(x+1, i);
    }

    //若这个皇后深搜后的结果不成功，则要返回原来的情况，八个方向都 --
	xx = x; yy = y;
    while(xx>0)  ch[xx--][y]--;
    xx = x; yy = y;
    while(yy>0)  ch[x][yy--]--;
    xx = x; yy = y;
    while(xx<=n) ch[xx++][y]--;
    xx = x; yy = y;
    while(yy<=n) ch[x][yy++]--;
    xx = x; yy = y;
    while(xx<=n && yy<=n) ch[xx++][yy++]--;
    xx = x; yy = y;
    while(xx>0  && yy<=n) ch[xx--][yy++]--;
    xx = x; yy = y;
    while(xx<=n && yy>0)  ch[xx++][yy--]--;
    xx = x; yy = y;
    while(xx>0  && yy>0)  ch[xx--][yy--]--;
}

void init()     //初始化函数
{
    int i, j;
    for(i = 0; i < 12; i++)
        for(j = 0; j < 12; j++)
            ch[i][j] = 0;
}

void set()
{
	int i, k;
	for(k = 1; k <= 10; k++)
	{
		num = 0; n = k;     //初始化
		for(i = 1; i <= k; i++)
        {
            init();         //初始化
            dfs(1, i);      //继续dfs寻找
        }
		result[k] = num;
	}
}

int main()
{
	set();
    while(scanf("%d", &n), n)
    {
        printf("%d\n", result[n]);
    }

    return 0;
}

 

评论

3 楼 breakallerror 2011-08-02  

太暴力了

2 楼 gzhu_101majia 2011-07-31  

lazykiki 写道

暴力搜索。。。

深搜是这样的吧 

1 楼 lazykiki 2011-07-31  

暴力搜索。。。