題目描述

在一個給定形狀的棋盤（形狀可能是不規則的）上面擺放棋子，棋子沒有區別。

要求擺放時任意的兩個棋子不能放在棋盤中的同一行或者同一列，請編程求解對于給定形狀和大小的棋盤，擺放 kk 個棋子的所有可行的擺放方案數目 CC。

輸入格式

輸入含有多組測試數據。

每組數據的第一行是兩個正整數 n,kn,k，用一個空格隔開，表示了將在一個 n?nn?n 的矩陣內描述棋盤，以及擺放棋子的數目。當為-1 -1時表示輸入結束。

隨后的 nn 行描述了棋盤的形狀：每行有 nn 個字符，其中 # 表示棋盤區域， . 表示空白區域（數據保證不出現多余的空白行或者空白列）。

輸出格式

對于每一組數據，給出一行輸出，輸出擺放的方案數目 CC （數據保證 C<231C<231）。

數據范圍

n≤8,k≤nn≤8,k≤n

輸入樣例：

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

輸出樣例：

2
1

代碼如下：

#include <bits/stdc++.h>
using namespace std;// 全局變量聲明
int res = 0;            // 結果，存儲可行方案數目
int nn = 0, number = 0; // nn為棋盤大小n，number為需要放置的棋子數k
vector<bool> v;         // 標記列是否被占用，v[i]為true表示第i列已被使用
vector<vector<char>> b; // 棋盤，存儲'#'和'.'，b[x][i]表示第x行第i列// 深度優先搜索函數
// 參數x：當前處理的行號，count：已放置的棋子數目
void dfs(int x, int count) {// 如果已放置number個棋子，方案數+1并返回if (count == number) {res++;return;}// 若超出棋盤行數，直接返回if (x > nn) {return;}// 遍歷當前行的所有列，嘗試放置棋子for (int i = 1; i <= nn; i++) {// 如果當前列未被占用且該位置可放置if (!v[i] && b[x][i] == '#') {v[i] = true;           // 標記該列為已使用dfs(x + 1, count + 1); // 遞歸處理下一行，棋子數+1v[i] = false;          // 回溯，撤銷列的標記}}// 不放置當前行的棋子，直接處理下一行dfs(x + 1, count);
}int main() {// 循環處理多組輸入，直到輸入-1 -1為止while (1) {cin >> nn >> number;if (nn == -1 && number == -1)break;// 初始化棋盤和標記數組b.assign(nn + 1, vector<char>(nn + 1, 0));v.assign(nn + 1, false);// 讀取棋盤數據，注意行和列從1開始存儲for (int i = 1; i <= nn; i++) {for (int j = 1; j <= nn; j++) {cin >> b[i][j];}}res = 0;            // 重置結果dfs(1, 0);           // 從第1行開始搜索，初始已放置0個棋子cout << res << endl; // 輸出當前棋盤的方案數}return 0;
}/*
思路詳解：
1. **問題分析**：在n×n棋盤的'#'位置放置k個棋子，要求任意兩個棋子不同行不同列。需要計算所有可行方案數。
2. **搜索策略**：采用深度優先搜索（DFS）逐行處理，每行有兩種選擇：放置或不放置棋子。
3. **放置規則**：- 在當前行選擇一個未被占用的列（對應'#'位置）。- 標記該列，遞歸處理下一行。- 回溯時撤銷列的標記，以嘗試其他可能的列。
4. **剪枝與終止條件**：- 當已放置k個棋子時，方案數+1。- 當處理完所有行時終止當前路徑。
5. **復雜度優化**：逐行處理避免行沖突，列標記數組避免列沖突，確保每行每列最多一個棋子。
6. **遞歸過程**：每次遞歸處理下一行，確保行號遞增，從而覆蓋所有行選擇組合。
*/

代碼說明

1. DFS 遞歸搜索
   • 遍歷當前行 x 的所有列，如果當前格子是 # 且該列未被占用，就放置棋子，并遞歸搜索下一行。
   • 不放置棋子，直接跳到下一行，保證搜索完整棋盤。
2. 回溯
   • 遞歸調用 dfs(x+1, count+1); 進入下一行。
   • 遞歸返回后，取消該列的占用狀態（v[i] = false;），以便嘗試其他方案。
3. 終止條件
   • 棋子數量等于 k：找到一種有效方案，res++ 并返回。
   • 超出行界限 x > n：無效路徑，直接返回。

---

時間復雜度分析

最壞情況下，n=8，k=8，即 8! ≈ 40,320，這種規模可以接受。