【簡單搜尋】棋盤問題

簡單棋盤問題

問題描述

在一個給定形狀的棋盤（形狀可能是不規則的）上面擺放棋子，棋子沒有差別。要求擺放時任意的兩個棋子不能放在棋盤中的同一行或者同一列，請程式設計求解對于給定形狀和大小的棋盤，擺放k個棋子的所有可行的擺放方案C。

輸入規範

輸入含有多組測試資料。 每組資料的第一行是兩個正整數，n k，用一個空格隔開，表示了将在一個n*n的矩陣内描述棋盤，以及擺放棋子的數目。

n <= 8 , k <= n 當為-1 -1時表示輸入結束。 随後的n行描述了棋盤的形狀：每行有n個字元，其中 # 表示棋盤區域， .

表示空白區域（資料保證不出現多餘的空白行或者空白列）。

輸出格式

對于每一組資料，給出一行輸出，輸出擺放的方案數目C （資料保證C<2^31）。

輸入樣例

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

輸出樣例

2 1

代碼樣例

//A-棋盤問題
#include<stdio.h>
#define MAXN 8
int n, k;
int counter, pieces;
int hash[MAXN]={0};
int board[MAXN][MAXN]={0}; 
void get_boardshape(){
	char str[MAXN][MAXN];
	for(int i=0; i<n; i++){
		scanf("%s", str[i]);
		for(int j=0; j<n; j++){
			if(str[i][j]=='#'){
				board[i][j]=1;
			}else{
				board[i][j]=0;
			}
			
		}
	}
}
void traverse(int level){
	if(pieces==k){
		counter++;
		return;
	}
	if(level>=n){
		return;
	}
	for(int j=0; j<n; j++){
		if(hash[j]==0 && board[level][j]==1 ){
			hash[j]=1;
			pieces++;
			traverse(level+1);
			hash[j]=0;
			pieces--;
		}
	}
	traverse(level+1);
}
int main(void){
	while(scanf("%d %d", &n, &k)==2 && (n!=-1 && k!=-1)){
		get_boardshape();
		traverse(0);
		printf("%d\n", counter);
		counter=0; 
	}
	return 0;
} 
           

函數解釋

擷取輸入的函數，同時将棋盤形狀存入數組board中。

• board[i][j]=0代表此位置不可落子
• board[i][j]=1代表此位置可以落子

起遞歸周遊作用的函數，主要有兩個層次的遞歸。這兩次遞歸相當于兩個指針。

思想是：

外層遞歸“指向”每個方案中的第一個棋子，内層遞歸“指向”方案中最後一個棋子的位置。

退層條件是目前落子數達到了預定的k值，方案數加1，退層後執行後續語句，恢複上文條件；而退出條件為遞歸層數level超過了board的行數（level從0開始計數）。

在内層遞歸中，使用了hash數組來記錄内層遞歸“指針”指向的目前層（行）前所有行的目前列是否有過落子。hash[i]=0，表示無落子；hash[i]=1，表示已有落子。

犯過的錯誤。。。

開始時為了少寫幾次int i和int j，我把i和j定義為了全局變量。而在traverse函數中使用到了變量j。。。

那麼問題就發生了。

traverse函數中的變量j應該是局部變量，在每次的退層結束後，會自動恢複進層前的狀态。但是這個j被窩定義成了全局變量，這意味着j的每次改變都是即時的、不可逆的。

在遞歸中，随進層和退層行為而被動改變的變量不該定義為全局變量。全局變量的生命周期太長了。

最後還是舍友給我指明了這點。感謝。

• 1605集訓任務
• 第一天任務完成