1.6.3 棋盤問題1

Description

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

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

Input

輸入含有多組測試數據。

每組數據的第一行是兩個正整數，n,k用一個空格隔開，表示了將在一個n?n的矩陣內描述棋盤，以及擺放棋子的數目。

當為?1?1時表示輸入結束。

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

Output

對于每一組數據，給出一行輸出，輸出擺放的方案數目CCC。

Sample Input 1

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

Sample Output 1

2 1

//DFS

//類似于八皇后的一道多了一些限制的題

#include

#include

#include

using namespace std;

const int N = 20;

char g[N][N]; //存儲輸入棋盤

int ans; //存儲答案

int n, k;

int m; //存儲已近放入棋盤的棋子數

bool line[N]; //存儲當前列上有沒有其他棋子

void dfs(int x)

{

if(m == k) //當棋子放光的時候

{

ans++;

return;

}

if(x == n) //防止越界

return;

for(int i = 0; i < n; i++) //直接dfs簡單完事 按著列的順序依次向下

if(!line[i] && g[x][i] == '#')

{

line[i] = true;

m++; //記錄放入的棋子數

dfs(x + 1);

line[i] = false; //還原初始狀態

m--;

}

dfs(x + 1);

//這個是關鍵，因為 k <= m，因此可能有的行不能放棋子，所以我們要手動舍棄行，直接進入下一行，以免有的情況被遺漏

}

int main()

{

while(scanf("%d%d", &n, &k) && n != -1 && k != -1)

{

ans = m = 0;

for(int i = 0; i < n; i++)

for(int j = 0; j < n; j++)

cin >> g[i][j];

dfs(0);

cout << ans << endl;

}

return 0;

}

大家可以比劃著自己手動模擬一下。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。