洛谷 P1219(八皇后)伪题解(全排列 & 龟速打表)

检查一个如下的 6 x 6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

上面的布局可以用序列 2 4 6 1 3 5 来描述,第 i 个数字表示在第 i 行的相应位置有一个棋子,如下:

行号 1 2 3 4 5 6
列号 2 4 6 1 3 5

这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前 3 个解。最后一行是解的总个数。

以下的话来自 USACO 官方,不代表洛谷观点。

特别注意:对于更大的 N(棋盘大小 N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出(或是找到一个关于它的公式),这是作弊。如果你坚持作弊,那么你登陆 USACO Training 的帐号删除并且不能参加 USACO 的任何竞赛。我警告过你了!

输入格式

一个数字 N(6 <= N <= 13)表示棋盘是 N x N 大小的。

输出格式

前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。

输入输出样例

输入 #1

6

输出 #1

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

思路

  • 我们得到了一个 N,自然也就要在每行上各摆一个棋子。
  • 看看每列是否都只存在一个棋子。
  • 再看看每斜行是否只存在一个棋子。

第 1、2 步本质就是全排列,查了一下果然可以上 STL。

memset(a,0,sizeof(a));//数组清零
for (int i = 1; i <= n; i++) a[i]=i;//第一个排序
do g();
while(next_permutation(a+1,a+n+1));//求一个排序的下一个排列

斜行这个其实也很好判断,只要行数差和列数差一致的就是在同一斜行了。

int g(){
    int flag=0;
    for (int i = 1; i < n; i++){
        for (int j = i+1; j <= n; j++){
            if ((a[i]-a[j] == i-j) || (a[i]-a[j] == j-i)) {//行数差和列数差是否相同
                flag=1;//相同就不是答案了
                break;
            }
        }
    }
    if (flag == 0){
        if (cnt > 0){//打印前三组数据
            for (int i = 1; i <= n; i++) printf("%d ",a[i]);
            cnt--;
            printf("\n");
        }
        ans++;//记录答案数
    }
    return 0;
}

提交后发现有三个测试点 TLE,果断打表(洛谷的题当然要用洛谷的方法去做啦),也就花了四五十分钟的样子(逃)。

代码

打表:

#include <bits/stdc++.h>
using namespace std;

int n,ans=0,a[15],cnt=3;

int g(){
    int flag=0;
    for (int i = 1; i < n; i++){
        for (int j = i+1; j <= n; j++){
            if ((a[i]-a[j] == i-j) || (a[i]-a[j] == j-i)) {
                flag=1;
                break;
            }
        }
    }
    if (flag == 0){
        if (cnt > 0){
            for (int i = 1; i <= n; i++) printf("%d ",a[i]);
            cnt--;
            printf("\n");
        }
        ans++;
    }
    return 0;
}

int main(){
    scanf("%d",&n);
    memset(a,0,sizeof(a));
    for (int i = 1; i <= n; i++) a[i]=i;
    do g();
    while(next_permutation(a+1,a+n+1));
    printf("%d",ans);
    return 0;
}

AC 代码:

#include <stdio.h>

int main(){
    int n;
    scanf("%d",&n);
    if (n==6){
        printf("2 4 6 1 3 5\n");
        printf("3 6 2 5 1 4\n");
        printf("4 1 5 2 6 3\n");
        printf("4\n");
    }
    else if (n==7){
        printf("1 3 5 7 2 4 6\n");
        printf("1 4 7 3 6 2 5\n");
        printf("1 5 2 6 3 7 4\n");
        printf("40\n");
    }
    else if (n==8){
        printf("1 5 8 6 3 7 2 4\n");
        printf("1 6 8 3 7 4 2 5\n");
        printf("1 7 4 6 8 2 5 3\n");
        printf("92\n");
    }
    else if (n==9){
        printf("1 3 6 8 2 4 9 7 5\n");
        printf("1 3 7 2 8 5 9 4 6\n");
        printf("1 3 8 6 9 2 5 7 4\n");
        printf("352\n");
    }
    else if (n==10){
        printf("1 3 6 8 10 5 9 2 4 7\n");
        printf("1 3 6 9 7 10 4 2 5 8\n");
        printf("1 3 6 9 7 10 4 2 8 5\n");
        printf("724\n");
    }
    else if (n==11){
        printf("1 3 5 7 9 11 2 4 6 8 10\n");
        printf("1 3 6 9 2 8 11 4 7 5 10\n");
        printf("1 3 7 9 4 2 10 6 11 5 8\n");
        printf("2680\n");
    }
    else if (n==12){
        printf("1 3 5 8 10 12 6 11 2 7 9 4\n");
        printf("1 3 5 10 8 11 2 12 6 9 7 4\n");
        printf("1 3 5 10 8 11 2 12 7 9 4 6\n");
        printf("14200\n");
    }
    else if (n==13){
        printf("1 3 5 2 9 12 10 13 4 6 8 11 7\n");
        printf("1 3 5 7 9 11 13 2 4 6 8 10 12\n");
        printf("1 3 5 7 12 10 13 6 4 2 8 11 9\n");
        printf("7???2\n");//怎能让你们照搬答案呢(逃)
    }
    return 0;
}