本次訓練聚焦于使用深度優先搜索（DFS）算法解決棋盤上的棋子擺放問題。題目要求在一個可能不規則的n×n棋盤上擺放k個棋子，且任意兩個棋子不能位于同一行或同一列。輸入包括棋盤大小n和棋子數k，以及棋盤的形狀（用#表示可放置區域，.表示空白）。輸出為所有可行的擺放方案數C。解題思路是通過DFS遍歷棋盤，標記已放置棋子的行和列，遞歸尋找所有可能的擺放方案，并在回溯時恢復標記。代碼實現中，使用二維數組表示棋盤，并通過兩個一維數組標記行和列的狀態。訓練強調了編碼習慣的養成和解題思維的訓練，為后續學習廣度優先搜索（BFS）算法打下基礎。
文章目錄
- 前言
- 一、題目
- 二、解題思路
- 總結
前言
本次訓練內容
- 訓練DFS處理棋盤問題。
- 對編碼習慣的養成。
- 訓練解題思維。
一、題目
????????在一個給定形狀的棋盤（形狀可能是不規則的）上面擺放棋子，棋子沒有區別。要求擺放時任意的兩個棋子不能放在棋盤中的同一行或者同一列，請編程求解對于給定形狀和大小的棋盤，擺放?k?個棋子的所有可行的擺放方案?C。
輸入格式
輸入含有多組測試數據。
每組數據的第一行是兩個正整數n,k，用一個空格隔開，表示了將在一個n×n的矩陣內描述棋盤，以及擺放棋子的數目。 (n≤8,k≤n)
當為?1?1時表示輸入結束。
隨后的n行描述了棋盤的形狀：每行有n個字符，其中 # 表示棋盤區域，. 表示空白區域（數據保證不出現多余的空白行或者空白列）。
輸出格式
對于每一組數據，給出一行輸出，輸出擺放的方案數目C（數據保證C<231）。
樣例輸入
2 1 #. .# 4 4 ...# ..#. .#.. #... -1 -1
樣例輸出
2 1
二、解題思路
? ? ? ? 今天的題目是一道基礎的DFS題，題目就是讓我遍歷棋盤，找到可以放置棋子的位置并放置對應的棋子，這步倒好做，直接定義標記點即可；然后就是讓它遞歸回溯，標記時要注意正負的順序。具體實現代碼如下：
#include <bits/stdc++.h>
using namespace std;
#define Max 10000
int n,k;
int sum=0;
char Array[Max][Max];
bool check[Max],check1[Max];//創建標記函數void DFS(int x) {if (x==0) {sum++;//計數器return;}for (int i=0;i<n;i++) {for (int j=0;j<n;j++) {if (Array[i][j]=='#'&&check[i]&&check1[j]) {//判斷是否可以放置棋子check[i]=check1[j]=false;//標記棋子Array[i][j]='.';//標記位置為不可用DFS(x-1);//遞歸check[i]=check1[j]=true;//回溯}}}
}
int main() {while (cin>>n>>k&&n!=-1&&k!=-1) {sum=0;for (int i=0;i<n;i++) {for (int j=0;j<n;j++) {cin>>Array[i][j];check[i]=true;//初始都可用check1[j]=true;}}DFS(k);cout<<sum<<endl;}}? ? ? ? while那里表示循環輸入，因為題中說明是通過-1來判斷是否結束。?
總結
? ? ? ? 今天的題目寫起來挺輕松的，沒有什么特別難想到的點；這段時間還得多推理一下那些搜索+回溯算法邏輯，這個思維的訓練可以讓我們更好的掌握DFS算法，進而去學習下一個BFS算法。后續在寫題時，還要多注意代碼習慣，不能因為一些小錯誤導致結果錯誤。
)
