【Tyvj1080】N 皇后

2014-05-23
竞赛题解 / 搜索
DFStyvj

描述 Description

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

列号

　　 1　 2　 3　 4　 5　 6

　　————————-

1 |　 | O |　 |　 |　 |　 |

　　————————-

2 |　 |　 |　 | O |　 |　 |

　　————————-

3 |　 |　 |　 |　 |　 | O |

　　————————-

4 | O |　 |　 |　 |　 |　 |

　　————————-

5 |　 |　 | O |　 |　 |　 |

　　————————-

6 |　 |　 |　 |　 | O |　 |

　　————————-

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

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

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

输入格式 InputFormat

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

输出格式 OutputFormat

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

样例输入 SampleInput

13

样例输出 SampleOutput

1 3 5 2 9 12 10 13 4 6 8 11 7
1 3 5 7 9 11 13 2 4 6 8 10 12
1 3 5 7 12 10 13 6 4 2 8 11 9
73712

来源 Source

USACO.

Tyvj 1080

代码 Code

水。跟评测机一比自测的速度不忍直视。。。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define fc(a) memset(a,0,sizeof(a))
int i,j,t,n,m,l,r,k,z,y,x,sum;
int a[15];
bool b[150],c[150],d[150];
void output()
{
    int i,j,t;
    sum++;
    if(sum<=3)
    {
        for(i=1;i<n;i++) printf("%d",a[i]);
        printf("%dn",a[n]);
    }
}
void queen(int k)
{
    int i,j,t;
    for (i=1;i<=n;i++)
    {
        if ((b[i]==0)&&(c[k+i]==0)&&(d[k-i+15]==0))
        {
            a[k]=i;
            b[i]=true;c[k+i]=true;d[k-i+15]=true;
            if (k==n) output();
            else queen(k+1);
            b[i]=false;c[k+i]=false;d[k-i+15]=false;
        }
    }
}
int main()
{
    fc(a);fc(b);fc(c);fc(d);
    scanf("%d",&n);
    queen(1);
    printf("%d\n",sum);
    return 0;
}