C++實作 1432. 棋盤挑戰
??大家好，我叫亓官劼（qí guān jié ），在CSDN中記錄學習的點滴歷程，時光荏苒，未來可期，加油~博主目前僅在CSDN中寫博客，唯一博客更新的地址為：亓官劼的博客 ，同時正在嘗試在B站中做一些內容分享，B站主頁為： 亓官劼的B站主頁
本文原創為亓官劼，請大家支持原創，部分平臺一直在惡意盜取博主的文章！！！
若需聯系博主，可以聯系本人微信：qiguanjie2015
題目
給定一個 N×N 的棋盤，請你在上面放置 N 個棋子，要求滿足：
- 每行每列都恰好有一個棋子
- 每條對角線上都最多只能有一個棋子
1 2 3 4 5 6
-------------------------
1 | | O | | | | |
-------------------------
2 | | | | O | | |
-------------------------
3 | | | | | | O |
-------------------------
4 | O | | | | | |
-------------------------
5 | | | O | | | |
-------------------------
6 | | | | | O | |
-------------------------
上圖給出了當 N=6 時的一種解決方案，該方案可用序列 2 4 6 1 3 5 來描述，該序列按順序給出了從第一行到第六行，每一行擺放的棋子所在的列的位置，
請你撰寫一個程式，給定一個 N×N 的棋盤以及 N 個棋子，請你找出所有滿足上述條件的棋子放置方案，
輸入格式
共一行，一個整數 N，
輸出格式
共四行，前三行每行輸出一個整數序列，用來描述一種可行放置方案，序列中的第 i 個數表示第 i 行的棋子應該擺放的列的位置，
這三行描述的方案應該是整數序列字典序排在第一、第二、第三的方案，
第四行輸出一個整數，表示可行放置方案的總數，
資料范圍
6≤N≤13
輸入樣例：
6
輸出樣例：
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
演算法思路
這里采用爆搜的思路，dfs，每次搜索的時候判斷當前是否可以放，搜索完成后回溯，恢復現場，
演算法實作
#include<iostream>
using namespace std;
const int N = 15;
int col[N],dg[N*2],udg[N*2],path[N];
int ans = 0,n;
void dfs(int x){
if(x > n){
ans++;
if(ans <= 3){
for(int i = 1 ; i <= n; i++)
cout<<path[i] << " ";
cout<<endl;
}
return ;
}
for(int i = 1; i <= n; i++){
if(!col[i] && !dg[i+x] && !udg[x-i+n]){
path[x] = i;
col[i] = dg[x + i] = udg[x - i + n] = 1;
// 向前搜索
dfs(x + 1);
// 狀態恢復
col[i] = dg[x + i] = udg[x - i + n] = 0;
path[x] = 0;
}
}
}
int main(){
cin >> n;
dfs(1);
cout<<ans;
return 0;
}
亓官劼
CSDN認證博客專家
Python
全堆疊
資料結構與演算法
CSDN認證博客專家
Python
全堆疊
資料結構與演算法
大家好，我是亓官劼(qí guān jié)，在博客中分享資料結構與演算法、Python全堆疊開發、Java后端開發、前端、OJ題解及各類報錯資訊解決方案等經驗，一起加油，用知識改變命運，未來可期，若有事項需聯系博主，可通過微信：qiguanjie2015 進行聯系，有慷訓回復，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/252080.html
標籤：AI
下一篇：Winlogbeat官方手冊學習