P1219 八皇后

題目描述

檢查一個(gè)如下的6 x 6的跳棋棋盤(pán)，有六個(gè)棋子被放置在棋盤(pán)上，使得每行、每列有且只有一個(gè)，每條對(duì)角線(包括兩條主對(duì)角線的所有平行線)上至多有一個(gè)棋子。

上面的布局可以用序列2 4 6 1 3 5來(lái)描述，第i個(gè)數(shù)字表示在第i行的相應(yīng)位置有一個(gè)棋子，如下：

行號(hào) 1 2 3 4 5 6

列號(hào) 2 4 6 1 3 5

這只是跳棋放置的一個(gè)解。請(qǐng)編一個(gè)程序找出所有跳棋放置的解。并把它們以上面的序列方法輸出。解按字典順序排列。請(qǐng)輸出前3個(gè)解。最后一行是解的總個(gè)數(shù)。

//以下的話(huà)來(lái)自u(píng)saco官方，不代表洛谷觀點(diǎn)

特別注意: 對(duì)于更大的N(棋盤(pán)大小N x N)你的程序應(yīng)當(dāng)改進(jìn)得更有效。不要事先計(jì)算出所有解然后只輸出(或是找到一個(gè)關(guān)于它的公式），這是作弊。如果你堅(jiān)持作弊，那么你登陸USACO Training的帳號(hào)刪除并且不能參加USACO的任何競(jìng)賽。我警告過(guò)你了！

輸入輸出格式

輸入格式：

?

一個(gè)數(shù)字N (6 <= N <= 13) 表示棋盤(pán)是N x N大小的。

?

輸出格式：

?

前三行為前三個(gè)解，每個(gè)解的兩個(gè)數(shù)字之間用一個(gè)空格隔開(kāi)。第四行只有一個(gè)數(shù)字，表示解的總數(shù)。

?

輸入輸出樣例

輸入樣例#1：?復(fù)制 6 輸出樣例#1：?復(fù)制 2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4

說(shuō)明

題目翻譯來(lái)自NOCOW。

USACO Training Section 1.5

?思路：搜索。

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,sum; int ans[14],check[3][28]; void dfs(int tot){if(tot>n){sum++;if(sum<=3){for(int i=1;i<=n;i++) printf("%d ",ans[i]);cout<<endl;}return ;}for(int i=1;i<=n;i++)if(!check[0][i]&&!check[1][tot+i]&&!check[2][tot-i+n]){ans[tot]=i;check[0][i]=1; check[1][tot+i]=1; check[2][tot-i+n]=1;dfs(tot+1);check[0][i]=0; check[1][tot+i]=0; check[2][tot-i+n]=0;} } int main(){scanf("%d",&n);dfs(1);printf("%d",sum); }

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/cangT-Tlan/p/8092659.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 P1219 八皇后的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。