【USACO】Checker Challenge题解！

Ethan · 发表于 2023-3-18 09:23:51

本帖最后由 Ethan 于 2023-3-19 09:17 编辑

简单来讲，就是八皇后问题。我们可以用深搜来解

注意!
题目要求只输出前三个解，最后一行才是总个数，而不是把所有方法都列举出来。

Ethan · 发表于 2023-3-19 09:18:36

本帖最后由 Ethan 于 2023-3-19 09:25 编辑

Jason1129 · 发表于 2023-3-19 09:20:37

:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol:lol

Ethan · 发表于 2023-3-19 09:25:50

oliver · 发表于 2023-3-22 00:43:56

题解思路

tiger · 发表于 2023-3-22 20:20:03

#include<iostream>
using namespace std;
int n=4,fangfa=0,a[14],num;
bool c[14],d[2*14],e[2*14];
void dfs(int x){
if(x==n){
      fangfa++;
      if(fangfa<=3){
         for(int i=1;i<=n;i++) cout<<a[i]<<" ";
         cout<<'\n';
      }
      return;
}
for(int i=1;i<=n;i++){
      if(!c[i]&&!d[n+x-i]&&!e[x+i]){
         a[x]=i;
         c[i]=d[n+x-i]=e[x+i]=1;
         dfs(x+1);
         c[i]=d[n+x-i]=e[x+i]=0;
      }
}
return;
}
int main(){
cin>>num;
n=num;
dfs(1);
cout<<fangfa;
return 0;
}