Poj (3239),m皇后问题

构造法很牛逼啊，把这个搜索的题直接变成了打表。

我用dfs写了一下。

构造法公式（序列）：
一、当n mod 6 != 2 或 n mod 6 != 3时：

[2,4,6,8,...,n],[1,3,5,7,...,n-1] (n为偶数)

[2,4,6,8,...,n-1],[1,3,5,7,...,n ] (n为奇数)
二、当n mod 6 == 2 或 n mod 6 == 3时

(当n为偶数,k=n/2；当n为奇数,k=(n-1)/2)

[k,k+2,k+4,...,n],[2,4,...,k-2],[k+3,k+5,...,n-1],[1,3,5,...,k+1]         (k为偶数,n为偶数)
[k,k+2,k+4,...,n-1],[2,4,...,k-2],[k+3,k+5,...,n-2],[1,3,5,...,k+1],[n]     (k为偶数,n为奇数)
[k,k+2,k+4,...,n-1],[1,3,5,...,k-2],[k+3,...,n],[2,4,...,k+1]              (k为奇数,n为偶数)
[k,k+2,k+4,...,n-2],[1,3,5,...,k-2],[k+3,...,n-1],[2,4,...,k+1],[n ]      (k为奇数,n为奇数)

这个规律我是没有搞懂的，反正很牛就是了。

我也用dfs写了一下，虽然我知道肯定会T，DFS30层就爆栈了，更何况这里是300层，就当是熟悉一下DFS了。

两种方法贴上。

#include <stdio.h>

#include <string.h>

int n;

int ans = ;

int maps[][] = {};

bool judge(int k,int i)

{

    for(int j=; j<=n&&j!=i; j++)

        if(maps[k][j]==)

            return false;

    for(int j=; j<=n&&j!=k; j++)

        if(maps[j][i]==)

            return false;

    for(int j=; k+j<=n&&i+j<=n; j++)

    {

        if(maps[k+j][i+j]==)

            return false;

    }

    for(int j=; k-j>=&&i-j>=; j++)

    {

        if(maps[k-j][i-j]==)

            return false;

    }

    for(int j=; k-j>=&&i+j<=n; j++)

    {

        if(maps[k-j][i+j]==)

            return false;

    }

    for(int j=; k+j<=n&&i-j>=; j++)

    {

        if(maps[k+j][i-j]==)

            return false;

    }

    return true;

}

bool dfs(int k)

{

    if(k>n)

    {

        ans ++;

        for(int i=; i<=n; i++)

        {

            for(int j=; j<=n; j++)

            {

                if(maps[i][j])

                    printf("%d",j);

            }

        }

        printf("\n");

        return true;

    }

    for(int i=; i<=n; i++)

    {

        if(judge(k,i))

        {

            maps[k][i] = ;

            if(dfs(k+))

                return true;

            maps[k][i] = ;

        }

    }

    return false;

}

int main()

{

    while(scanf("%d",&n),n)

    {

        memset(maps,,sizeof(maps));

        for(int i=; i<=n; i++)

        {

            maps[][i] = ;

            if(dfs())

                break;

            maps[][i] = ;

        }

        //printf("%d\n",ans);

    }

    return ;

}

#include <stdio.h>

int main()

{

    int n;

    while(scanf("%d",&n),n)

    {

        if(n%!=&&n%!=)

        {

            if(n%==)

            {

                for(int i=;i<=n;i+=)

                    printf("%d ",i);

                for(int i=;i<=n-;i+=)

                    printf("%d ",i);

                printf("%d\n",n-);

            }

            else {

                for(int i=;i<=n-;i+=)

                    printf("%d ",i);

                for(int i=;i<=n-;i+=)

                    printf("%d ",i);

                printf("%d\n",n);

            }

        }

        else

        {

            if(n%==)

            {

                int k=n/;

                if(k%==)

                {

                    for(int i=k;i<=n;i+=)

                        printf("%d ",i);

                    for(int i=;i<=k-;i+=)

                        printf("%d ",i);

                    for(int i=k+;i<=n-;i+=)

                        printf("%d ",i);

                    for(int i=;i<=k-;i+=)

                        printf("%d ",i);

                    printf("%d\n",k+);

                }

                else

                {

                    for(int i=k;i<=n-;i+=)

                        printf("%d ",i);

                    for(int i=;i<=k-;i+=)

                        printf("%d ",i);

                    for(int i=k+;i<=n;i+=)

                        printf("%d ",i);

                    for(int i=;i<=k-;i+=)

                        printf("%d ",i);

                    printf("%d\n",k+);

                }

            }

            else

            {

                int k=(n-)/;

                if(k%==)

                {

                    for(int i=k;i<=n-;i+=)

                        printf("%d ",i);

                    for(int i=;i<=k-;i+=)

                        printf("%d ",i);

                    for(int i=k+;i<=n-;i+=)

                        printf("%d ",i);

                    for(int i=;i<=k+;i+=)

                        printf("%d ",i);

                    printf("%d\n",n);

                }

                else

                {

                    for(int i=k;i<=n-;i+=)

                        printf("%d ",i);

                    for(int i=;i<=k-;i+=)

                        printf("%d ",i);

                    for(int i=k+;i<=n-;i+=)

                        printf("%d ",i);

                    for(int i=;i<=k+;i+=)

                        printf("%d ",i);

                    printf("%d\n",n);

                }

            }

        }

    }

    return ;

}

巴特西

Poj (3239),m皇后问题

最新文章

热门文章