牛客網 NC16407 題解：托米航空公司的座位安排問題

題目分析

解題思路

本題可以采用深度優先搜索(DFS)來解決：

1. 從左上角開始，按行優先順序遍歷每個座位
2. 對于每個座位，有兩種選擇：
   • 選擇該座位（如果滿足條件）
   • 不選擇該座位
3. 使用二維數組 st[][] 記錄座位狀態
4. 當選擇了 K 個座位時，方案數加1

代碼詳解

#include <bits/stdc++.h>
using namespace std;// 全局變量定義
int n, m, k, ans;  // n行m列，選擇k個座位，ans記錄答案
const int N = 90;  // 數組大小
const int P = 420047;  // 取模數
int st[N][N];  // 記錄座位狀態// DFS函數：x,y表示當前位置，u表示已選擇的座位數
void dfs(int x, int y, int u) {// 如果已經選擇了k個座位，方案數+1if(u == k) {ans++;ans %= P;return;}// 如果當前列超出范圍，移動到下一行第一列if(y > m) {y = 1;x++;}// 如果所有位置都遍歷完，返回if(x > n) return;// 嘗試選擇當前位置if(!st[x-1][y] && !st[x][y-1]) {  // 檢查上方和左方是否為空st[x][y] = 1;  // 標記為已選dfs(x, y+1, u+1);  // 繼續搜索下一個位置st[x][y] = 0;  // 回溯，取消選擇}// 不選擇當前位置，繼續搜索dfs(x, y+1, u);
}int main() {int t;cin >> t;  // 讀入測試用例數while(t--) {cin >> n >> m >> k;  // 讀入行列數和需要選擇的座位數ans = 0;  // 初始化答案dfs(1, 1, 0);  // 從(1,1)開始搜索cout << ans % P << endl;  // 輸出結果}return 0;
}

算法分析

1. 時間復雜度：O(2^(M*N))，最壞情況下需要遍歷所有可能的組合
2. 空間復雜度：O(M*N)，主要用于存儲座位狀態數組

優化建議

1. 可以添加剪枝優化，比如：

   • 當剩余未遍歷的座位數小于還需要選擇的座位數時，直接返回
   • 可以預處理每個位置可以選擇的座位數，提前判斷是否可能達到目標

2. 對于大規模數據，可以考慮使用動態規劃或狀態壓縮DP來優化

注意事項

1. 數組大小要開夠，題目中說明 N*M <= 80，所以開90足夠
2. 注意取模運算，每次更新答案時都要取模
3. 回溯時要記得恢復狀態

總結

這道題目是一個典型的DFS回溯問題，通過合理的狀態記錄和回溯，可以有效地求解所有合法的座位安排方案。代碼實現簡潔，但要注意細節處理，如邊界條件和狀態恢復。