【洛谷 P1219】[USACO1.5]八皇后 Checker Challenge 题解(深度优先搜索+回溯法)

简介: **USACO1.5八皇后挑战**是关于在$n\times n$棋盘上放置棋子的,确保每行、每列及两条主对角线上各有一个且仅有一个棋子。给定$6$作为输入,输出前$3$个解及解的总数。例如,对于$6\times6$棋盘,正确输出应包括解的序列和总数。代码使用DFS解决,通过跟踪对角线占用状态避免冲突。当找到所有解时,显示前三个并计数。样例输入$6$产生输出为解的前三个排列和总数$4$。

[USACO1.5]八皇后 Checker Challenge

题目描述

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

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

行号 $1\ 2\ 3\ 4\ 5\ 6$

列号 $2\ 4\ 6\ 1\ 3\ 5$

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

输入格式

一行一个正整数 $n$,表示棋盘是 $n \times n$ 大小的。

输出格式

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

样例 #1

样例输入 #1

6

样例输出 #1

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

提示

【数据范围】
对于 $100\%$ 的数据,$6 \le n \le 13$。

题目翻译来自NOCOW。

USACO Training Section 1.5

思路

用棋子的坐标转换得到棋子所在的对角线编号,每个棋子占据一条主对角线和一条副对角线,下一个棋子不能放在已被占据的对角线上。

AC代码

#include <iostream>
#include <cstring>
#define ms(a) memset(a, 0, sizeof(a))
#define AUTHOR "HEX9CF"
using namespace std;

const int maxn = 1005;

int n;
int a[maxn];
bool b[maxn], diag1[maxn], diag2[maxn];
int cnt = 0;

void dfs(int x)
{
   
   
    if (n == x)
    {
   
   
        cnt++;
        if(4 > cnt){
   
   

            for (int i = 0; i < n; i++)
            {
   
   
                cout << a[i] << " ";
            }
            cout << endl;
        }
    }
    for (int i = 1; i <= n; i++)
    {
   
   
        int d1 = n - x + i;
        int d2 = x + i;
        if (!b[i] && !diag1[d1] && !diag2[d2])
        {
   
   
            b[i] = 1;
            diag1[d1] = 1;
            diag2[d2] = 1;
            a[x] = i;
            dfs(x + 1);
            b[i] = 0;
            diag1[d1] = 0;
            diag2[d2] = 0;
        }
    }
}

int main()
{
   
   
    ms(a);
    ms(b);
    ms(diag1);
    ms(diag2);
    cin >> n;
    dfs(0);
    cout << cnt << endl;
    return 0;
}
目录
相关文章
codeforces 272C. Dima and Staircase(线段树)
题目很长,看加猜加谷歌翻译才看懂了题目。每级台阶的宽都是1,但高不同,并且告诉你了,然后给你m个箱子,长和宽都告诉你,把箱子靠左放,求箱子的底部有多高。
28 0
华为机试HJ44:Sudoku(数独问题,深度优先遍历DFS解法)
华为机试HJ44:Sudoku(数独问题,深度优先遍历DFS解法)
128 0
|
11月前
|
算法 测试技术
每日一题:LeetCode-LCR 143.子结构判断
每日一题:LeetCode-LCR 143.子结构判断
Codeforces1153——D. Serval and Rooted Tree(思维好题+dfs+贪心)
Codeforces1153——D. Serval and Rooted Tree(思维好题+dfs+贪心)
129 0
Codeforces1153——D. Serval and Rooted Tree(思维好题+dfs+贪心)
AtCoder Beginner Contest 216 G - 01Sequence (并查集 贪心 树状数组 差分约束)
AtCoder Beginner Contest 216 G - 01Sequence (并查集 贪心 树状数组 差分约束)
151 0
|
定位技术
HDOJ/HDU 1180 诡异的楼梯(经典BFS-详解)
HDOJ/HDU 1180 诡异的楼梯(经典BFS-详解)
130 0
HDOJ/HDU 1180 诡异的楼梯(经典BFS-详解)
[解题报告]《算法零基础100讲》(第15讲) 二分快速幂
[解题报告]《算法零基础100讲》(第15讲) 二分快速幂
[解题报告]《算法零基础100讲》(第15讲) 二分快速幂
|
人工智能
Codeforces-1260-E. Tournament贪心
题意: 有n个人,第i个人有力量值i,这n个人中,每次对局两两之间进行solo,如果说一个人的力量之大于他的对手,这个人是赢的,赢得比赛的选手会进入下一轮比赛中。 然而里面有一个人为你的朋友,他或许并不是里面最强的人,要想让朋友成为冠军,就需要对必要的人进行贿赂,求出最少需要花费多少才能使得朋友成为冠军。在每次对局中,都可以进行任意的对局安排,对局安排只取决于自己
96 0