1.5.4 Checker Challenge跳棋的挑战

1.5.4 Checker Challenge跳棋的挑战

时间: 1ms        内存:64M

描述:

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

列号

0   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个解。最后一行是解的总个数。

特别注意: 对于更大的N(棋盘大小N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出,这是作弊。如果你坚持作弊,那么你登陆USACO Training的帐号将被无警告删除

输入:

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

输出:

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

示例输入:

6

示例输出:

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

提示:

参考答案(内存最优[752]):

/*
ID:zhaofuk1
PROG: checker
LANG: C
*/
#include<stdio.h>
#include<string.h>
int n, tot = 0;
int digit[20], vis[3][50];
void dfs(int cur)
{
    int i, j;
    if(cur == n){
        tot++;
        if(tot < 4){
            for(i = 0; i < n; i++){
                if(i != 0)
                    printf(" ");
                printf("%d", digit[i] + 1);
            }
            printf("\n");
        }
    }else for(i = 0; i < n; i++){
        if(!vis[0][i] && !vis[1][cur + i] && !vis[2][cur + n - i]){
            digit[cur] = i;
            vis[0][i] = vis[1][cur + i] = vis[2][cur + n - i] = 1;
            dfs(cur + 1);
            vis[0][i] = vis[1][cur + i] = vis[2][cur + n - i] = 0;
        }
    }

}

int main()
{
    int i, j, k;
    //freopen("checker.in", "r", stdin);
    //freopen("checker.out", "w", stdout);
    scanf("%d", &n);
    memset(vis, 0, sizeof(vis));
    dfs(0);
    printf("%d\n", tot);
    return 0;
}

参考答案(时间最优[344]):

/*
ID:zhaofuk1
PROG: checker
LANG: C
*/
#include<stdio.h>
#include<string.h>
int n, tot = 0;
int digit[20], vis[3][50];
void dfs(int cur)
{
    int i, j;
    if(cur == n){
        tot++;
        if(tot < 4){
            for(i = 0; i < n; i++){
                if(i != 0)
                    printf(" ");
                printf("%d", digit[i] + 1);
            }
            printf("\n");
        }
    }else for(i = 0; i < n; i++){
        if(!vis[0][i] && !vis[1][cur + i] && !vis[2][cur + n - i]){
            digit[cur] = i;
            vis[0][i] = vis[1][cur + i] = vis[2][cur + n - i] = 1;
            dfs(cur + 1);
            vis[0][i] = vis[1][cur + i] = vis[2][cur + n - i] = 0;
        }
    }

}

int main()
{
    int i, j, k;
    //freopen("checker.in", "r", stdin);
    //freopen("checker.out", "w", stdout);
    scanf("%d", &n);
    memset(vis, 0, sizeof(vis));
    dfs(0);
    printf("%d\n", tot);
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注