P1219 [USACO1.5] 八皇后 Checker Challenge

Yama-lei2025年3月14日大约 3 分钟

P1219 [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

输出 #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

我的答案：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
vector<P> queens;
int n;
int solutions=0;
inline bool contradict(P p1, P p2){
    return p1.first==p2.first||p1.second==p2.second||p1.first-p1.second==p2.first-p2.second||p1.first+p1.second==p2.first+p2.second;
}
bool couldPlace(P p){
    for(P queen:queens){
        if(contradict(queen,p)){
            return false;
        }
    }
    return true;
}
void print(){
    for(P p:queens){
        cout<<p.second+1<<" ";
    }
    cout<<endl;
}

bool find_P(int row,int start=0){
    bool found=false;
    for(int col=start;col<n;col++){
            P newQueen(row,col);
            if(couldPlace(newQueen)){
                queens.push_back(newQueen);
                found=true;
                if(row!=n-1&&!find_P(row+1)){
                    queens.pop_back();
                    found=false;
                }
                if(found){
                    break;
                }
            }
    }
    if(found){
        if(row==n-1){
            solutions+=1;
            if(solutions<=3){
                print();
            }
        }
        int col=queens.back().second;
        queens.pop_back();
        find_P(row,col+1);
    }
    return found;
}   
int main(){
    cin>>n;
    find_P(0,0);
    cout<<solutions;
    return 0;
}

上学期课上讲过八皇后问题，但是讲得实在没听懂；时隔几个月再来挑战，成功了；

P2392 kkksc03考前临时抱佛脚

题目背景

kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。

题目描述

这次期末考试，kkksc03 需要考 $4$ 科。因此要开始刷习题集，每科都有一个习题集，分别有 $s_1,s_2,s_3,s_4$ 道题目，完成每道题目需要一些时间，可能不等（$A_1,A_2,\ldots,A_{s_1}$，$B_1,B_2,\ldots,B_{s_2}$，$C_1,C_2,\ldots,C_{s_3}$，$D_1,D_2,\ldots,D_{s_4}$）。

kkksc03 有一个能力，他的左右两个大脑可以同时计算 $2$ 道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。

由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。