【洛谷 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;
}
目录
相关文章
华为机试HJ44:Sudoku(数独问题,深度优先遍历DFS解法)
华为机试HJ44:Sudoku(数独问题,深度优先遍历DFS解法)
132 0
UVa668 - Parliament(贪心)
UVa668 - Parliament(贪心)
56 0
|
机器学习/深度学习 Windows
The 2022 ICPC Asia Regionals Online Contest (I)-D题题解(DFS暴搜+剪枝+打表去重+二分)
时间复杂度:O(227 + nlog(n) + T * log(n)),227是DFS打表的时间,nlog(n)是vertor排序的时间,T*log(n)是询问次数和二分搜答案的时间。(如果算错了,评论或者私信指出谢谢)
168 0
The 2022 ICPC Asia Regionals Online Contest (I)-D题题解(DFS暴搜+剪枝+打表去重+二分)
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 (并查集 贪心 树状数组 差分约束)
152 0
|
人工智能
Codeforces-1260-E. Tournament贪心
题意: 有n个人,第i个人有力量值i,这n个人中,每次对局两两之间进行solo,如果说一个人的力量之大于他的对手,这个人是赢的,赢得比赛的选手会进入下一轮比赛中。 然而里面有一个人为你的朋友,他或许并不是里面最强的人,要想让朋友成为冠军,就需要对必要的人进行贿赂,求出最少需要花费多少才能使得朋友成为冠军。在每次对局中,都可以进行任意的对局安排,对局安排只取决于自己
96 0
|
人工智能
codeforces1143B Nirvana(贪心)
codeforces1143B题解(贪心)
975 0
|
算法 BI
约瑟夫问题(Josephus problem)的klog(n)解法
约瑟夫问题是一个经典的算法问题,其解决过程涉可能用到的数据结构有数组、链表,涉及的算法包括模拟、递归、递推、动态规划等等,因此非常适合做一道面试题。   问题描述: 首先n个候选人围成一个圈,依次编号为0..n-1。然后指定一个正整数k,并0号候选人开始按从1到k的顺序依次报数,n-1号候选人报数之后,又再次从0开始。当有人报到K时,这个人被淘汰,从圈里出去。下一个人从1开始重新报
4379 0