Yui的狗窝
Yui的狗窝
hdoj 2553 N皇后问题 暴力回溯

原题:http://acm.hdu.edu.cn/showproblem.php?pid=2553
“回溯法”我觉得很能体现这种算法的思想,想了个比较通俗(好玩)的讲法:玩rpg的时候免不了要存档,看看这个boss打不打的过。如果死了,我们就得读上一个档;如果没死,我们还可以继续用这个存档苟下去。
引申到搜索遍历上,假如此路不通,我们就回到之前的记录点,开始尝试其他的路径;如果能走我们就继续走下去。

#include<iostream>
using namespace std;
bool map[11][11];
int res[11];
int t;
long long tem;
bool check(int x,int y,int n)
{
    if(x<1||x>n||y<1||y>n)
        return false;
    if(map[x][y])
        return false;
    for(int i=1;i!=n+1;i++)
        if(map[i][y]||map[x][i])
            return false;
    for(int i=1;i<n;i++)
    {
        if(x-i>=1&&x-i<=n&&y-i>=1&&y-i<=n)
            if(map[x-i][y-i])
                return false;
        if(x-i>=1&&x-i<=n&&y+i>=1&&y+i<=n)
            if(map[x-i][y+i])
                return false;
        if(x+i>=1&&x+i<=n&&y-i>=1&&y-i<=n)
            if(map[x+i][y-i])
                return false;
        if(x+i>=1&&x+i<=n&&y+i>=1&&y+i<=n)
            if(map[x+i][y+i])
                return false;
    }
    return true;
}
void dfs(int a,int n)
{
    if(a>n)
    {
        tem++;
        return;
    }
    else
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                if(check(i,j,n))
                {
                    map[i][j]=true;
                    dfs(a+1,n);
                    map[i][j]=false;
                }
            }
    }
}
int f(int a)
{
    int tem1=a,ans=1;
    for(int i=1;i<=a;i++)
        ans*=(tem1--);
    return ans;
}
int main()
{
    for(int i=1;i!=11;i++)
    {
        tem=0;
        memset(map,false,sizeof(map));
        dfs(1,i);
        res[i]=tem/f(i);
    }
    while(cin>>t)
        cout<<res[t]<<endl;
}
</code>
这是我认为能够很好的体现上面思想的代码,但是很可惜这波代码le,因为在枚举到8以后数据量太大了,还是必须剪枝。
仔细看一眼题目描述,我们可以得知棋盘为正方形。当点(i,j)存在了一枚皇后,我们可以得到第i行与第j列必定不存在皇后,这样就省去了许多不必要的遍历点。
代码如下:
<code lang="cpp">
#include<iostream>
using namespace std;
int res[11],map[11];
int t,tem;
int dfs(int a,int n)
{
    bool flag;
    if(a>n)
        return ++tem;
    else
    {
        for(int i=1;i<=n;i++)
        {
            map[a]=i;
            flag=true;
            for(int j=1;j<a;j++)
            {
                if(map[j]==i||i-a==map[j]-j||i+a==map[j]+j)
                {
                    flag=false;
                    break;
                }
            }
            if(flag)
                dfs(a+1,n);
        }
    }
}
int main()
{
    for(int i=1;i!=11;i++)
    {
        tem=0;
        dfs(1,i);
        res[i]=tem;
    }
    while(cin>>t,t)
        cout<<res[t]<<endl;
}

题外话:暑假里写完的时候觉得很开心,感觉自己弄懂了回溯法~但是在语言表达上还是有点问题……

没有标签
首页      算法训练      hdoj 2553 N皇后问题 暴力回溯
https://secure.gravatar.com/avatar/d0fe7f1b17d5e9122db921e3a8cc327f?s=256&d=mm&r=g

Suzumiya, Yui

文章作者

发表评论

textsms
account_circle
email

Yui的狗窝

hdoj 2553 N皇后问题 暴力回溯
原题:http://acm.hdu.edu.cn/showproblem.php?pid=2553 “回溯法”我觉得很能体现这种算法的思想,想了个比较通俗(好玩)的讲法:玩rpg的时候免不了要存档,看看这个boss打不打的过。如果死…
扫描二维码继续阅读
2017-10-31


没有激活的小工具